■シュタイナーのピザ切り分け問題(その4)

(問)1つの円を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

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

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

個の断片ができます.

 もうひとつのバージョンでは

  Sn=(n,0)+(n,1)+(n,2)=(n^2+n+2)/2

  Sn=(n+1,2)+1=(n^2+n+2)/2

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

 オイラーの公式を使って,ピザ切り分け問題を解くために,頂点と辺を数えると,2n個の境界頂点とnC2=n(n−1)/2個の内部頂点があるから

  e=2n+n(n−1)/2

 また,ピザの境界上にn本の曲線状の辺とn本のカットはそれぞれn本の直線の辺を含んでいるから

  v=2n+n^2

 よって,

  f=e−v+1=(n^2+n+2)/2

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

(問)1つの円をn本の弦で分割する.その際,分割によってできる領域が最も多くなるようにする.円と共通点をもつピースの個数Pnはいくつになるか?

  P1=2,P2=4,P3=6,P4=8,P5=10

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

  Pn=Pn-1+2

  Pn=2n

 逆に,円と共通点をもたないピースの個数Qnは

  Qn=Sn−Pn=(n^2+n+2)/2−2n

あるいは,もうひとつのバージョンでは

  Qn=(n,0)−(n,1)+(n,2)=(n^2+n+2)/2−2n

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