六角形の対角線の交点数は１５個であるが，正六角形では対角線の交点は１３個しかない．正多角形の対角線の交点の数がいくつあるかという問題は一見単純そうにみえるのですが，３本以上の対角線が１点で交わる場合を考慮しなければならないので，古くから難問として知られているそうです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【Ｑ１】凸ｎ角形の対角線の本数は？

　ひとつの頂点から引ける対角線はｎ−３本．また，頂点はｎ個あるから，ｎ（ｎ−３）本のように思えるが，これでは同じ対角線が重複して数えられているから２で割って，Ｌ＝ｎ（ｎ−３）／２本．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【Ｑ２】凸ｎ角形の対角線の交点数の最大値は？

　凸ｎ角形の対角線の交点数の最大値がいくつになるか考えてみることにします．４つの頂点で２本の対角線の交点がひとつ定まりますから，ｎ個の頂点から４つを選ぶ組み合わせ数

　　Ｉmax＝nＣ4

となります．六角形では１５個になる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【Ｑ３】正ｎ角形の対角線の交点数の最大値は？

　正ｎ角形の対角線をすべて引いたときのグラフの頂点数の最大値は

　　Ｖ＝ｎ＋Ｉmax

また，対角線がひとつの交点により分割される断片の数は１交差する毎に２個増えますから，グラフの辺数の最大値は

　　Ｅ＝ｎ＋Ｌ＋２Ｉmax

　分割数の最大値Ｒmaxは

　　Ｖ＝ｎ＋Ｉmax

　　Ｅ＝ｎ＋Ｌ＋２Ｉmax

　　Ｆ＝Ｒmax＋１

をオイラーの多面体公式：Ｖ−Ｅ＋Ｆ＝２に代入すると

　　Ｒmax＝Ｌ＋Ｉmax＋１＝（ｎ−１）（ｎ−２）（ｎ^2−３ｎ＋１２）／２４

　この問題は次の問題と等価になります．

　　Ｒmax＝Ｍn−ｎ

　　Ｍn＝n-1Ｃ0＋n-1Ｃ1＋n-1Ｃ2＋n-1Ｃ3＋n-1Ｃ4

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【Ｑ４】円の最大分割数

（問）円周上にｎ点をとり，円周上の点同士をすべて互いに弦で結ぶ．その際，円の分割によってできる領域が最も多くなるようにする．最大分割領域数Ｍnはいくつになるか？

（答）Ｍ1＝１，Ｍ2＝２は明らか．また，円に内接する三角形，四角形，五角形を描くと

　　Ｍ3＝４，Ｍ4＝８，Ｍ5＝１６

このことから，

　　Ｍn＝２^(n-1)

であると予想されます．しかし，この式ではＭ0＝１／２となってしまい，Ｍ0＝１とならないことが気にかかるところです．

　ｎ＝６の場合を実際にやってみると，正六角形のように３本の線が１点で交わってしまう場合は最大領域数にならないのでＮＧですが，第６の点が既存の弦の交点を通らないように注意すると，Ｍ6＝３２ではなく，Ｍ6＝３１となることがわかります．

　ここで

　　Ｍn＝２^(n-1)

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

　　Ｍ7＝５７，Ｍ8＝９９，Ｍ9＝１６３

となり，数列

　　｛１，２，４，８，１６，３１，５７，９９，１６３，・・・｝

は，公比２の等比数列

　　｛１，２，４，８，１６，３２，６４，１２８，２５６，・・・｝

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

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

　　４＝３＋１，８＝４＋４

　円周上に５点がある場合は五角形の外側に５つの領域，すぐ内側に１０個の三角形領域，中心部に五角形がひとつある．

　　１６＝５＋１０＋１

　円周上に６点がある場合は六角形の外側に６つの領域，すぐ内側に１８個の三角形領域，その内側に３つの五角形と３つの四角形，そして中心部に三角形がひとつある．

　　３１＝６＋１８＋６＋１

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

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

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

には，すべての領域にラベルを与えると，ラベルを含む数の個数は０，１，２，３，４のいずれかであって，２項係数の和

　　Ｍn＝n-1Ｃ0＋n-1Ｃ1＋n-1Ｃ2＋n-1Ｃ3＋n-1Ｃ4

　　　 ＝１＋（ｎ−１）＋（ｎ−１）（ｎ−２）／２＋（ｎ−１）（ｎ−２）（ｎ−３）／６＋（ｎ−１）（ｎ−２）（ｎ−３）（ｎ−４）／２４

　　　 ＝（ｎ^4−６ｎ^3＋２３ｎ^2−１８ｎ＋２４）／２４　

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

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

　　n-1Ｃ0＋n-1Ｃ1＋n-1Ｃ2＋n-1Ｃ3＋n-1Ｃ4＋・・・＋n-1Ｃn-1＝２^(n-1)

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

　　Ｍ1＝１，Ｍ2＝２，Ｍ3＝４，Ｍ4＝８，Ｍ5＝１６，

　　Ｍ6＝３１，Ｍ7＝５７，Ｍ8＝９９，Ｍ9＝１６３，Ｍ10＝２５６，

　　Ｍ11＝３８６，Ｍ12＝５６２，Ｍ13＝７９４，Ｍ14＝１０９３，

　　Ｍ15＝１４７１，Ｍ16＝１９４１，Ｍ17＝２５１７，Ｍ18＝３２１４，

　　Ｍ19＝４０４８，Ｍ20＝５０３６，Ｍ21＝６１９６，Ｍ22＝７５４７，

　　Ｍ23＝９１０９，Ｍ24＝１０９０３，Ｍ25＝１２９５１，Ｍ26＝１５２７６，

　　Ｍ27＝１７９０２，Ｍ28＝２０８５４，Ｍ29＝２４１５８，Ｍ30＝２７８４１，

　　Ｍ31＝３１９３１，・・・

　数列

　　｛Ｍn｝＝｛１，２，４，８，１６，３１，５７，９９，１６３，・・・｝

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

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝