円周上の点を選んで円を分割しますか？

Question

円上では、Nの円周上で任意の点が選択されます。 Nポイントで形成された完全なグラフは、円の面積を多くの部分に分割します。

ポイントを円周に沿って選択したときに円が分割される領域の最大数はいくらですか？

例：

• 2ポイント=> 2枚
• 4点=> 8枚

任意のアイデアこれについて移動する方法？

Answer 1

これは、Moser's circle problemとして知られています。

溶液である：

すなわち

証拠は非常に単純である：

は、円内の各交点を考えます。 2つの線の交点によって定義されなければならず、各線には2つの点があるため、円内のすべての交点は円周上に4つの固有の点集合を定義します。したがって、最大でn choose 4の内側の頂点があり、明らかに円周上にnの頂点があります。

ここで、各頂点はいくつの辺に触れていますか？さて、それは完全なグラフなので、外側の各頂点はn - 1のエッジに接触し、内側の各頂点は4のエッジに接触します。したがって、辺の数は(n(n - 1) + 4(n choose 4))/2で与えられます（それ以外の場合、各辺は2つの頂点で2回カウントされるため、2で割る）。

最後のステップでは、グラフ内の面の数、つまりv - e + f = 1（このケースではEuler characteristic）にオイラーの公式を使用します。 fについて解く

はピーターアレキサンダーの優れた答えが正しい答えであれば、それは、この完全グラフのエッジが線分でなければならない制約を言及する必要があります:-)