領域

３次元空間をｎ枚の平面で分割するときできる空間領域の最大個数D(n)を求めよ。
平面を直線や放物線で分割した時のD(n)は解ったのですがこの問題は想像するのが難しく解けませんでした。教えてもらえたら幸いです。

No.2 ベストアンサー 回答者： hogehogeninja 回答日時： 2003/05/12 00:13

些細ですが、ちょっと間違いがありますね。

２次元のときのS(n)を求める予備考察のところで、n+1本目の直線が採ることの出来る線分の最大数はn-2ではなくてn-1ですね。
漸化式も間違っていますが、S(n) の答えはあっているようです。
失礼しました。

この回答へのお礼

ありがとうございました！

お礼日時：2006/01/20 01:42

No.3 回答者： tancoro 回答日時： 2003/05/14 17:19

有限領域（体積のある領域）の数に関しては、hogehogeninja さんが回答していらっしゃるので、『領域』を無限領域（体積が∞の領域）まで含めた場合について考えて見ました。

(1) 直線の分割
まず、１本の直線を n個の点で分割した場合を考えます。
この場合は、新たに加える点によって、そこの領域が２つに分断されていきます。
最大領域数 R(n) は、
R(n) = n + 1


(2) 平面の分割
次に、平面を n本の直線で分割した場合を考えます。
この場合は、n本目の直線は n-1本の直線と交わり、且つ、n-1個の交点が存在します。
(1)よりこの直線は R(n-1) の領域に分断され、さらに、そのR(n-1)個 の線により平面領域が各々２つに分断される。
結果的に R(n-1) 領域が増加すると言えます。
平面の最大領域 S(n)は、
S(n) = R(n-1) + S(n-1)
= n + S(n-1)
= Σk + S(0)
= n(n+1)/2 + 1


(3) 空間の分割
最後に、空間を n枚の平面で分割した場合を考えます。
この場合は、n枚目の平面は n-1枚の平面と交わる。その時、この平面上には n-1本の直線ができる。
(2)よりこの平面は S(n-1) の領域に分断され、さらに、そのS(n-1)個の面により空間領域が各々２つに分断される。
つまり、S(n-1)領域が増加するといえます。
空間の最大領域 T(n)は、
T(n) = S(n-1) + T(n-1)
= (n-1)((n-1)+1)/2 + 1 + T(n-1)
= n(n-1)/2 + 1 + T(n-1)
= (1/2)Σk^2 - (1/2)Σk + n + T(0)
= n(n+1)(2n+1)/12 - n(n+1)/4 + n + 1


※ 式中のΣは(k=1 ～ n)を表すものとします。

No.1 回答者： hogehogeninja 回答日時： 2003/05/11 23:49

平面をｎ個の直線で分割するとき、出来る領域の最大値をS（ｎ）とします。

いま、ｎ本の直線でS(ｎ）個の領域があるときします。
このとき、端点以外では他の直線と交わらないような線分は、必ず１つ領域を増やします（ただしｎ＞＝２のとき）
n+1本目の直線を引くとき、このような線分は、n+1本目の直線上に最大でn-2本とることができます。

よって、S(n+1) = S(n) + (n-2)　
と漸化式が求まり、
S(n) = (1/2)(n-2)(n-1)
となるわけですね。

ポイントは、端点以外では直線と交わらない線分１つが、新たな領域を１つ区切り、一つ領域を増やす役割をすることです。

これを３次元のときに考えると、この線分の役割をするのは、辺以外の内部で他の面とは交わらない、２次元多角形領域です。
ですので、n枚の平面でD(n)個の３次元領域があるとき、n+1枚目の平面を加えたときに追加される３次元領域の数は、n+1枚目の平面上で、他の平面と交わることによって出来る２次元領域の数に等しいはずです。

ですので、n+1枚目の平面を加えたときに追加される３次元領域の 最 大 の数は、n+1枚目の平面上で、他の平面と交わることによって出来る２次元領域の 最 大 の数に等しいです。

ここから
D(n+1) = D(n) + S(n)
と漸化式が立ち、
D(n) = (1/4)(n-3){(1/3)(n-2)(2n-5)+n-4}
となりそうです。