モーザーの円分割問題

幾何学においてモーザーの円分割問題^[1]（モーザーのえんぶんかつもんだい、英: dividing a circle into areas, Moser's circle problem）は円に内接する $n$ 角形の辺と対角線（円の弦）によって分割される円の領域の個数の最大化問題である。レオ・モーザーに因み名づけられ、帰納法などで解決されている。領域の個数の最大値は $r_{G}={n \choose 4}+{n \choose 2}+1$ （ $(n k)$ は二項係数）によって表される。 $r G$ の数列 1, 2, 4, 8, 16, 31, 57, 99, 163, 256（オンライン整数列大辞典の数列 A000127）はモーザー数列と呼ばれる^[2]。最初の5項は等比数列 $2 n - 1$ だが $n = 6$ でこの規則から外れており、少数の観察で一般化することの危険性（少数の強法則（英語版））を示している^[3]。

補題

円の上に $n$ 点を用意し、新たな1点 $A$ を取り円上を動かす。 $A$ ともとの $n$ 点を結ぶことにより $n$ つの線分を描く。今、新たに描いた線分が、もとの $n$ 点をそれぞれ結ぶ線分の交点のどれかを通る場合（これを $a$ とする）と、新たに書いた線分がもとの $n$ 点をそれぞれ結ぶ線分と先のどの交点とも異なる場所で交わる場合（これを $b$ とする）が考えられる。

補題: 円上に新たな点 $A$ を、場合 $b$ が起こるように定めることが可能である。

証明: 場合 $a$ では、 $A$ 、 $n$ 点のうちの1点 $O$ 、 $n$ 点をそれぞれ結ぶ線分のうち2つの交点 $I$ の3点が一直線上に存在する。 $O$ の取り方は $n$ 通りあるので $I$ の取り方も有限個となる。直線 $OI$ は $O$ と異なる点で再度円と交差するが、円上にはいくらでも多くの点が存在するから、 $A$ をどの直線 $OI$ 上にもない点として定めることができる。したがってこのような場合の点 $A$ とすべてのもとの $n$ 点 $O$ について場合 $b$ が実現される。

この補題は、 $k$ 本の線分が $AO$ と交わるとき、 $k$ 本の線分と $AO$ の交点をすべて異なる場所で交わるように設置し、新たに $k + 1$ 個の領域を生むことができることを意味する。

問題の解

帰納法

補題によって問題の解決のための重要な性質が確立された。数学的帰納法を用いて $n - 1$ 点の場合の領域の個数の最大値 $f (n - 1)$ により、 $n$ 点の場合の領域の個数の最大値 $f (n)$ を表現する。

図の実線の1, 2, 3, 4の点を通る線分は円を8つの領域に分割している（すなわち $f (4) = 8$ ）。図は $n = 4$ の場合から、破線を加えた $n = 5$ の場合を導くことを説明している。1, 2, 3, 4の点から5の点へ新たに4つの線分が結ばれている。この4線分の出現によって新しく生まれた領域の個数を数える。

一般に、図の1, 2, 3, 4のように数 $i$ を定める。新たな点とどの点とを結ぶか（ $i$ の値）に応じて、交差する既存の弦の本数が変わる。また、新たに加えられた弦同士は新たに取った1点以外の点で交わることはない。

新しい点と点 $i$ を結ぶ新たな弦が交わる既存の弦の個数は、新たな弦の「左側」にある点の個数と「右側」にある点の個数によって定められる。任意の既存の点はそれら同士が線分で結ばれているから、「左側」にある既存の点の個数と「右側」にある既存の点の個数の積は、円の内部で新しい弦と交わる既存の弦の個数と等しい。点 $i$ について、 $n - i - 1$ 個の点が「左側」に存在し $i - 1$ 個の点が「右側」に存在するとしたとき、円の内部で新たな弦と交わる既存の弦は $(n - i - 1)(i - 1)$ 本ある。

たとえば図（ $n = 5$ ）において $i = 1$ の場合と $i = 4$ の場合、つまり1と5、4と5を結ぶ線分は円の内部にて他のどの線分とも交わっていない。一方 $i = 2, i = 3$ の場合は、円の内部にて、もとの線分のうち2つと交わっている。

新たな弦に交わる既存の弦らが成している領域の個数は、弦の個数に1を加えた値と等しい。新たに加えた弦によってそれぞれの領域は2つに分割されるので、次の式が成立する。

f(n)=f(n-1)+\sum _{i=1}^{n-1}{\big (}1+(n-i-1)(i-1){\big )}.

展開して、

f(n)=f(n-1)+\sum _{i=1}^{n-1}(2-n+ni-i^{2}).

1から $n - 1$ までの自然数及びその平方の総和を計算して、

f(n)=f(n-1)+{\frac {1}{6}}n^{3}-n^{2}+{\frac {17}{6}}n-2.

漸化的に、

f(n)=\sum _{k=1}^{n}\left({\frac {1}{6}}k^{3}-k^{2}+{\frac {17}{6}}k-2\right)+1,

ただし $f (0) = 1$ 。計算して、

f(n)={\frac {n}{24}}(n^{3}-6n^{2}+23n-18)+1.

^[4]

組み合わせと位相幾何学による方法

$(n k)$ の $n$ （行）と $k$ （列）	0	1	2	3	4	総和
1	1	—	—	—	—	1
2	1	1	—	—	—	2
3	1	2	1	—	—	4
4	1	3	3	1	—	8
5	1	4	6	4	1	16
6	1	5	10	10	5	31
7	1	6	15	20	15	57
8	1	7	21	35	35	99
9	1	8	28	56	70	163
10	1	9	36	84	126	256
パスカルの三角形の各段の1項目から5項目までの総和の列

先の補題は、"内部の"交点がどれも単純（どの3つの弦も円の内部で共点でない）ならば、領域の個数が最大値をとることを示している。これは点を一般の位置（英語版）に置いた場合であるといえる。一般の位置にあるという仮定の下、領域の個数は（ここでは2次元球面に埋め込まれたグラフとしてみなすことができる）連結（英語版）平面グラフのオイラー標数の公式を用いて数えることができる。

連結平面グラフが $F$ 個の面、 $E$ 個の辺、 $V$ 個の頂点で平面を分割したとする。このとき、2次元球面において、オイラーの関係式より、

\,V-E+F=2

である。弦と円の図を平面グラフと見なす。 $V, E$ の決定によって $F$ も定まることからこの問題を解決する。

円上の $n$ 点を外部の頂点、弦の交点を内部の頂点とする。一般の位置にあるという仮定により、3本以上の弦が共点となることはない。

$V$ の決定のためには内部の頂点の数を調べることが必要となる。補題より"一般の位置"の仮定が達成されている配置であるとできる。今、外部の頂点の中から4点を取ったとき、その4点を頂点とする円に内接する（凸）四角形の対角線の交点として内部の頂点がただ1つ決まることが分かる。逆にすべての内部の頂点は外部の頂点の4点の唯一の組と対応させることができる。

したがって内部の頂点は4つの外部の頂点を選ぶ組み合わせに等しいのであり^[5]、

V_{\text{interior}}={n \choose 4},

と計算できる。ゆえに、

V=V_{\text{exterior}}+V_{\text{interior}}=n+{n \choose 4}.

平面グラフの辺 $E$ には、隣接する外部の頂点を結ぶ延べ $n$ 個の円弧と、外部の頂点を結んでできる弦を交点で分割したものが含まれる。外部、内部という頂点の分類から弦は次の3種類に分類できる。

2つの外部の頂点を結ぶ、他の弦とは交わらない弦。隣り合う外部の頂点を結ぶ弦がこれにあたる。円に内接する $n$ 角形の辺となることから、計 $n$ 本ある。
2つの内部の頂点を結ぶ線分（辺）。
内部の点と外部の点を結ぶ線分（辺）。

グループ2, 3の辺の個数を求めるため、ある特定の4つの辺と繋がる内部の頂点を考える。このとき、

4{n \choose 4}

個の辺が見つかる。各辺は2つの端点の頂点によって定義される。内部の頂点のみが数え上げられたから、グループ2の辺は2回数えられ、グループ3の辺は1回のみ数えられている。

他の弦と交わる弦（グループ1に含まれない弦）は、始点または終点と内部の点とを端点に持つ辺、つまりグループ3の辺を2つ含む。弦は外部の頂点2つによって決定されるから、グループ3の辺は、

2\left({n \choose 2}-n\right)

個ある。これはグループ1に含まれない弦の総数の2倍の数である。

これらの結果によってグループ2, 3の辺の個数を計算できる。グループ1の辺 $n$ つと元の円の円弧 $n$ つを加えて辺の総和は、

E={\frac {4{n \choose 4}+2\left({n \choose 2}-n\right)}{2}}+n+n=2{n \choose 4}+{n \choose 2}+n.

$V, E$ の値をオイラーの関係式 $F = E - V + 2$ に代入して

F={n \choose 4}+{n \choose 2}+2.

このうち1面は円の外部を指すから、円の内部の分割領域の個数 $r G$ は $F - 1$ である。したがって、

r_{G}={n \choose 4}+{n \choose 2}+1,

二項係数を階乗で表すことにより、

r_{G}={\frac {n!}{(n-4)!4!}}+{\frac {n!}{(n-2)!2!}}+1

この式を変形すれば、帰納法を用いて証明した式と同じ四次式が表れる^[6]。

r_{G}={\frac {1}{24}}n(n^{3}-6n^{2}+23n-18)+1

ベルヌーイの三角形（英語版）の5列目（ $k = 4$ ）は $3 < n$ において、 $n + 1$ の場合のモーザーの円分割問題の解である。

円内で反射する粒子の軌跡

円内において粒子の力を与えない運動を考えたとき、円周にて粒子が特定の角度で跳ねかえるとすると、粒子の軌跡に関連する円分割の数列が等差級数で与えられる^[7]。

均等な点の配置

4より大きい偶数個の場合で点が均一に並べられているとき、領域の個数は減少する。オンライン整数列大辞典の数列 A006533。

n	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	...
r_G	1	2	4	8	16	31	57	99	163	256	386	562	794	1093	1471	1941	2517	3214	4048	5036	6196	7547	9109	10903	12951	...
r_G′	1	2	4	8	16	30	57	88	163	230	386	456	794	966	1471	1712	2517	2484	4048	4520	6196	6842	9109	9048	12951	...

正整数 $n$ の階乗の正の約数の個数は $n = 1, 2,...,6$ のときこの数列と一致するが、 $n = 6$ から先は異っている^[8]。

出典

^ 竹山, 美宏『定理のつくりかた』森北出版、2018年2月、38頁。ISBN 978-4-627-06231-3。
^ ウリーン 2011; 中村 2013.
^ Guy, R. K. (1988). “The Strong Law of Small Numbers”. Amer. Math. Monthly 95: 697-712.
^ Yaglom & Yaglom 1964; Conway & Guy 1996.
^ 北島 2011.
^ Jobbings 2008; Le Goff 2012.
^ Jaud, D. (2022). “Integer Sequences from Circle Divisions by Rational Billiard Trajectories”. Proceedings of the 20th International Conference on Geometry and Graphics. doi:10.1007/978-3-031-13588-0_8.
^ A027423