■意外な難問(その4)

【Q6】円の最大分割数(おまけ)

(問)1つの円をn本の弦で分割する.その際,分割によってできる領域が最も多くなるようにする.最大分割領域数Snはいくつになるか?

(答)パンケーキをnスライスしたときの最大ピース数を求めよという問題ですが,この問題は実は円という条件を取り去っても同じ答えになります.すなわち,平面をn本の線で分割する.その際,分割によってできる領域が最も多くなるようにする.最大分割領域数Snはいくつになるか?

 分割される領域数が最大になるためには,新しい線(弦)を引くとき,それ以前のすべての線(弦)と新しい交点で交わるようにします.既存の交点を通ると分割される領域が最大数にならないからです.

  S0=1,S1=2,S2=4,S3=7

はすぐに求められます.このことからn本目の線(弦)を引くと新しい領域がn個増えることがわかります.これを式で表すと

  Sn=Sn-1+n

  Sn=Sn-1+n

  Sn-1=Sn-2+n−1

  ・・・・・・・・・・

  S1=S0+1

  S0=1

を辺々加えると,一般式

  Sn=1+(1+2+3+・・・+n)=1+n(n+1)/2

    =(n^2+n+2)/2

が得られます.

  S0=1,S1=2,S2=4,S3=7,

  S4=11,S5=16,S6=22,S7=29,

  S8=37,S9=46,S10=56,・・・

と続くというわけです.

 パンケーキではなく,ケーキをnスライスしたときの最大ピース数を求めよという問題では,

  Sn=(n+2)(n+3)/6

  S0=1,S1=2,S2=4,S3=8,

  S4=15,S5=26,S6=42,S7=64,

  S8=93,S9=130,S10=176,・・・

===================================