■シュタイナーのピザ切り分け問題(その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
===================================