空間の分割数                             戻る

 東京工業大学の入試問題(2019年度)に空間の分割数を問う問題が出題された。「難し
い!」と巷間を賑わした問題のようで、少し興味があり解いてみた。


 東京工業大学 前期理系(2019)(改題)

 空間の相異なるn枚の平面によって、いくつの空間領域に分割される。この分割数の最大
値を求めよ。


 n=1、2、3 について、具体的に分割数の最大値を求めてみよう。

 n 枚の平面による分割数の最大値をHとおく。

 H1=2 、H2=4 、H3=8 であることは明らかだろう。


 実は、この問題を解くためには、次の問題が大いに関係してくる。

 「平面上において異なる n 本の直線が一般の位置にあるものとする。これらの直
 線で平面はいくつに分割されるか?


は、漸化式を用いて解く有名問題である。n 本の直線による平面の分割数をLとおく。

 例えば、 L1=2 、L2=4 、L3=7 であることは明らかだろう。

問題 次の図において、平面はいくつに分割されているか?

    左図において、 L5=16 である。

    上記の値はもちろん数え上げてもよいが、次のよう
   に計算できる。

    L3=L2+3=4+3=7

    L4=L3+4=7+4=11

    L5=L4+5=11+5=16

 一般の位置にある直線による平面の分割数を問う問題は「ケーキ数の問題」と言われ、そ
のとき出来る数列

 2、4、7、11、15、・・・

は、「lazy cateree's sequence」(怠けた仕出し屋数列)と言われる。

 ケーキを分割する最大個数は、

 p=(n2+n+2)/2=1+(n2+n)/2=n0n+12n0n1n2

で与えられる。


 このとき、東京工業大学の問題は、次の漸化式を解く問題に帰着される。

 H1=2 、H2=4 、Hn+1=L+H

 L1=2 、L2=4 、Ln+1=L+n+1

 n≧2のとき、 L=L1+(2+3+・・・+n)=(n2+n+2)/2

 この式は、n=1のときも成り立つ。

 よって、n≧2のとき、 H=H1+Σk=1n-1k=(n3+5n+6)/6

 この式は、n=1のときも成り立つ。



   以下、工事中