Делить круг на части, выбирая точки по окружности?

Question

На окружности N произвольные точки выбираются на его окружности.Полный график, сформированный из этих N точек, разделил бы область круга на множество частей.

Каково максимальное количество частей области, на которые круг будет разделен, когда точкивыбираются по окружности?

Примеры:

• 2 балла => 2 шт.
• 4 балла => 8 шт.

Есть идеи, как это сделать?

Answer 1

Это известно как проблема круга Мозера .

Решение:

1010 * т.е. *

Доказательство довольно простое:

Рассмотрим каждое пересечение внутри круга. Он должен быть определен пересечением двух линий, и каждая линия имеет две точки, поэтому каждое пересечение внутри круга определяет 4 уникальных набора точек на окружности. Следовательно, существует не более n choose 4 внутренних вершин и, очевидно, на окружности n вершин.

Теперь, сколько ребер касается каждая вершина? Ну, это полный граф, поэтому каждая внешняя вершина касается n - 1 ребер, и, конечно, каждая внутренняя вершина касается 4 ребер. Таким образом, число ребер задается как (n(n - 1) + 4(n choose 4))/2 (мы делим на два, потому что в противном случае каждое ребро будет учитываться дважды по двум его вершинам).

Последний шаг - использование формулы Эйлера для числа граней в графе, т. Е. v - e + f = 1 ( характеристика Эйлера равна 1 в нашем случае).

Решение для f дает формулы выше: -)