■ベン図・オイラー図(その19)

(問)円周上にn点をとり,円周上の点同士をすべて互いに弦で結ぶ(n点は同一円周上に等間隔に配置されているとは限らない).その際,円の分割によってできる領域が最も多くなるようにする.最大分割領域数Mnはいくつになるか?

(答)M1=1,M2=2は明らか.また,円に内接する三角形,四角形,五角形を描くと

  M3=4,M4=8,M5=16

このことから,

  Mn=2^(n-1)

であると予想されます.しかし,この式ではM0=1/2となってしまい,M0=1とならないことが気にかかるところです.

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

 n=6の場合を実際にやってみると,正六角形のように3本の線が1点で交わってしまう場合は最大領域数にならないのでNGですが,第6の点が既存の弦の交点を通らないように注意すると,M6=32ではなく,M6=31となることがわかります.

 ここで

  Mn=2^(n-1)

は間違いであることに気づかされるのですが,さらに

  M7=57,M8=99,M9=163,M10=256,M11=386

となり,数列

  {1,2,4,8,16,31,57,99,163,256,386,・・・}

は,公比2の等比数列

  {1,2,4,8,16,32,64,128,256,・・・}

から大きく離れていきます.

 それでは一般式はどのように表されるのでしょうか? 図を描きながらパターンを探してみると,円周上に3点がある場合は三角形の外側に3つの領域,内側に1つの領域,4点の場合は四角形の外側に4つの領域,内側に4つの領域ができる.

  4=3+1,8=4+4

 円周上に5点がある場合は五角形の外側に5つの領域,すぐ内側に10個の三角形領域,中心部に五角形がひとつある.

  16=5+10+1

 円周上に6点がある場合は六角形の外側に6つの領域,すぐ内側に18個の三角形領域,その内側に3つの五角形と3つの四角形,そして中心部に三角形がひとつある.

  31=6+18+6+1

 しかしこのパターンからはどうしてもこれといったアイディアが浮かばないのですが,領域の数は弦の数や交点の数と関係していることは明らかであって,前者はnC2,後者はnC4で計算されます.

 図なしにこれ以上説明することは難しいので,結論を述べますが

  [参]コンウィイ・ガイ「数の本」シュプリンガー・フェアラーク東京

には,すべての領域にラベルを与えると,ラベルを含む数の個数は0,1,2,3,4のいずれかであって,2項係数の和

  Mn=n-1C0+n-1C1+n-1C2+n-1C3+n-1C4

    =1+(n−1)+(n−1)(n−2)/2+(n−1)(n−2)(n−3)/6+(n−1)(n−2)(n−3)(n−4)/24

    =(n^4−6n^3+23n^2−18n+24)/24 

となることが示されています.

 パスカルの三角形のはじめの5項の和というわけですが,

  n-1C0+n-1C1+n-1C2+n-1C3+n-1C4+・・・+n-1Cn-1=2^(n-1)

ですから,nが大きくなればその答えは2^(n-1)からますます離れていくというわけです.

  Mn=n-1C0+n-1C1+n-1C2+n-1C3+n-1C4

  Mn=n+nC4+n-1C2

  Mn=nC4+nC2+1

  M1=1,M2=2,M3=4,M4=8,M5=16,

  M6=31,M7=57,M8=99,M9=163,M10=256,

  M11=386,M12=562,M13=794,M14=1093,

  M15=1471,M16=1941,M17=2517,M18=3214,

  M19=4048,M20=5036,M21=6196,M22=7547,

  M23=9109,M24=10903,M25=12951,M26=15276,

  M27=17902,M28=20854,M29=24158,M30=27841,

  M31=31931,・・・

 数列

  {Mn}={1,2,4,8,16,31,57,99,163,・・・}

をこの問題を提起したモーザーにちなんでモーザー数列と呼ぶことにすると,モーザー数列は先入観から間違った答えを予想してしまう例としてしばしば引き合いにだされるものになっています.

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

【1】もうひとつのバージョン

  Mn=n+nC4+n-1C2

  Mn=nC4+nC2+1=(n,4)+(n,2)+(n,0)

 円内にnC4個の交点,nC2個の弦があることから,辺数は

  2nC4+nC2+n

オイラーの公式により,領域の個数は

  Mn+n=2nC4+nC2+n−nC4+2

  Mn=(n,4)+(n,2)+(n,0)

となる.

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