■円の切断(その3)

【3】ピザの最大分割数

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

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

 ピザの中心を通るように3カットすると6切れになりますが,少しずらすと7切れできます.分割される領域数が最大になるためには,新しい線を引くとき,それ以前のすべての線と新しい交点で交わるようにします.既存の交点を通ると分割される領域が最大数にならないからです.

  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

が得られます.すなわち,一般公式ではn回切った場合,

  n(n+1)/2+1=(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,・・・

と続くというわけです.

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