円を領域に分割する

幾何学において、 n辺を持つ内接多角形を使って円を領域に分割し、辺と対角線で作られる領域の数が最大になるような分割問題。モーザーの円問題(レオ・モーザーにちなんで名付けられました) とも呼ばれ、帰納的方法で解くことができます。領域の最大可能数は、1、2、4、8、16、31、57、99、163、256 、... という数列になります ( OEIS : A000127 )。最初の 5 つの項は等比数列2 ⁿ − ^{1と一致しますが、} n = 6で外れており、少数の観察のみから一般化することのリスクを示しています。 ${\displaystyle r_{G}={n \choose 4}+{n \choose 2}+1}$

円上にn 個の点があり、さらに 1 個の点を追加すると、新しい点から既存の点までn本の線を引くことができます。2 つのケースが考えられます。最初のケース ( a ) では、新しい線は 2 本以上の古い線 (既存の点間) が交差する点を通過します。2 番目のケース ( b ) では、新しい線は古い線のそれぞれと異なる点で交差します。次の事実を知っておくと役立ちます。

補題.新しい点Aは、新しい各線に対して ケースbが発生するように選択できます。

証明。ケースaの場合、 3 つの点が 1 つの直線上になければなりません。新しい点A 、直線が引かれる古い点O 、および 2 本の古い直線が交差する点Iです。古い点Oはn 個あるため、 2 本の古い直線が交差する点I は有限個あります。各OおよびIについて、直線OI はO以外の 1 つの点で円と交差します。円には無限個の点があるため、どの直線OI上にもならない点Aが存在します。したがって、この点Aとすべての古い点Oについて、ケースb が真になります。

この補題は、 AO を横切る線がk本ある場合、それぞれの線はAO を異なる点で横切り、 線AOによってk + 1 個の新しい領域が作成されることを意味します。

この補題は問題を解くための重要な性質を確立する。帰納的証明を用いることで、 f ( n − 1) を用いてf ( n )の式を得ることができる。

図では、濃い線が点 1 から 4 を結び、円を合計 8 つの領域 (つまり、f (4) = 8) に分割しています。この図は、破線でn = 4からn = 5 への帰納的ステップを示しています。5 番目の点が追加されると (つまり、 f ( 4) を使用してf (5) を計算すると)、接続先の点ごとに 1 つずつ、1 から 4 の番号が付けられた 4 つの新しい線 (図の破線) が追加されます。したがって、5 番目の点によって導入される新しい領域の数は、4 つの線のそれぞれによって追加される領域の数を考慮することで決定できます。追加される線をカウントするには、 i を設定します。新しい線はそれぞれ、その点 ( iの値) に応じて、既存の線の数と交差できます。新しい線は、新しい点以外では互いに交差することはありません。

それぞれの新しい線が交差する線の数は、線の「左側」にある点の数と線の「右側」にある点の数を考慮することで決定できます。既存のすべての点の間にはすでに線が通っているため、左側の点の数と右側の点の数を掛け合わせたものが、新しい線と交差する線の数です。点iへの線については、次のようになります。

n − i − 1

左側の点と

私− 1

右側のポイントなので合計は

( n − i − 1) ( i − 1)

境界線を越えなければならない。

この例では、 i = 1 とi = 4への線はそれぞれ 0 本の線と交差しますが、 i = 2 とi = 3への線はそれぞれ 2 本の線と交差します (片側に 2 つの点があり、反対側に 1 つの点があります)。

したがって、再発は次のように表される。

${\displaystyle f(n)=f(n-1)+\sum _{i=1}^{n-1}{\big (}1+(ni-1)(i-1){\big )},}$

これは簡単に

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

最初の自然数と最初の平方数の和を使うと、 ${\displaystyle (n-1)}$${\displaystyle (n-1)}$

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

ついに、

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

その結果

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

この補題は、弦の「内部」交差点がすべて単純である場合（内部の各交差点を弦が 2 本ずつ通過する場合）、領域の数が最大になると主張しています。これは、円上の点が「一般的な位置」で選択された場合に当てはまります。この「一般的な交差点」の仮定の下では、連結平面グラフ（ここでは 2球面S ²に埋め込まれたグラフとして表示）のオイラー特性の式を使用して、非帰納的な方法で領域の数を決定することもできます。

平面グラフは、 F面（2次元セル）、E辺（1次元セル）、V頂点（0次元セル）を持つ平面のセル分解を決定します。グラフが接続されているため、2次元球面S ²のオイラー関係式は

${\displaystyle \,V-E+F=2}$

が成り立ちます。上の図 (円とすべての弦) を平面グラフとして見てください。VとEの両方の一般式がわかれば、 Fの式も導き出され、問題が解決します。

頂点には、外部頂点と呼ばれる円上のn点と、円の内部にある異なる弦の交点である内部頂点が含まれます。上記の「一般的な交点」の仮定により、各内部頂点は 2 本以下の弦の交点であることが保証されます。

したがって、 V を決定する主なタスクは、内部頂点の数を見つけることです。補題の結果として、任意の 2 つの交差する弦は、内部頂点を一意に決定します。これらの弦は、弦の対応する 4 つの端点 (すべて外部頂点) によって一意に決定されます。任意の 4 つの外部頂点は、巡回四辺形を決定し、すべての巡回四辺形は凸四辺形であるため、4 つの外部頂点の各セットには、対角線 (弦) によって形成される交点が 1 つだけあります。さらに、定義により、すべての内部頂点は交差する弦によって形成されます。

したがって、各内部頂点は4つの外部頂点の組み合わせによって一意に決定され、内部頂点の数は次のように表される。

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

など

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

エッジには、隣接する外部頂点のペアを接続するn 個の円弧と、弦の集合によって円の内側に作成される弦線分 (以下で説明) が含まれます。頂点には外部と内部の 2 つのグループがあるため、弦線分はさらに 3 つのグループに分類できます。

1. 2 つの外部頂点を直接接続する (他の弦によって切断されない) エッジ。これらは隣接する外部頂点間の弦であり、ポリゴンの周囲を形成します。このようなエッジはn個あります。
2. 2 つの内部頂点を接続するエッジ。
3. 内部頂点と外部頂点を接続するエッジ。

グループ2と3の辺の数を求めるには、ちょうど4つの辺に接続されている各内部頂点を考えます。これは次の式になります。

${\displaystyle 4{n \choose 4}}$

エッジ。各エッジは 2 つの端点頂点によって定義されるため、内部頂点のみが列挙され、グループ 2 のエッジは 2 回カウントされ、グループ 3 のエッジは 1 回だけカウントされます。

他のコード（グループ1に属さないコード）によって切断されるすべてのコードには、グループ3の2つのエッジ、つまり開始と終了のコードセグメントが含まれている必要があります。コードは2つの外部頂点によって一意に決定されるため、

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

グループ 3 のエッジ。これは、グループ 1 のメンバーではないコードの合計数の 2 倍です。

これらの結果の合計を2で割ると、グループ2と3のエッジの合計数が得られます。グループ1のn個のエッジとn個の円弧エッジを追加すると、合計は次のようになります。

${\displaystyle 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について解いたオイラーの関係に代入すると、次の式が得られる。 ${\displaystyle \,F=E-V+2,}$

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

これらの面の1つは円の外側にあるので、円の内側の領域r _Gの数はF − 1、つまり

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

これは次のように解決される

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

これは帰納的方法を用いて得られるのと同じ4次多項式を与える。

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

ベルヌーイの三角形の 5 番目の列( k = 4) は、円をn + 1 点の領域に分割する問題における領域の最大数を示します ( n ≥ 4)。

円内の粒子の力のない運動を考慮すると、円の境界に沿った特定の反射角度に対して、関連する面積分割シーケンスが等差級数で与えられることが示されました (D. Jaud を参照)。

点が円の周囲に均等に配置されている場合には、 n > 4でも 領域の数は減少し、OEISシーケンスA006533が得られる: ^[2]

n > 0の場合のnの約数の数は1、2、4、8、16、30から始まりますが、次の項（60、96、160、270、540、792、...）は上記とは異なります。^[3]

• ケーキ番号
• 怠け者の仕出し屋のシーケンス– ここでn は直線カットの数です
• ピザ定理

• Conway, JHおよびGuy, RK「地域はいくつあるか」『The Book of Numbers』ニューヨーク: Springer-Verlag、pp. 76–79、1996 年。
• Weisstein、Eric W.「弦による円の分割」。MathWorld。
• http://www.arbelos.co.uk/Papers/Chords-regions.pdf 2011-09-04 にWayback Machineにアーカイブされました
• Jaud, D.「有理ビリヤード軌道による円分割からの整数シーケンス」。「ICGG 2022 - 第20回国際幾何学およびグラフィックス会議の議事録」、DOI: 10.1007/978-3-031-13588-0_8