Разбиение круга прямыми

[denny]

Решалась задачка:
На окружности расставлено $n$ точек, попарно соединенных линиями.
На какое максимальное число областей $A_n$ можно разделить круг?

Педагогический смысл задачи в том, что для $n = 1, 2, 3, 4$ прямым подсчетом получается $A_n = 2^{n-1}$
А для $n=5 $ находим $31$, т.е. $2^{n-1} - 1$
Тогда как в общем случае $A_n = (24 - 18 n + 23 n^2 - 6 n^3 + n^4)/24$
Этот результат находится по индукции, в полной аналогии с классической задачей
о разбиении плоскости прямыми.

Далее возникают вопросы.
Если точки будут вершинами правильного n-угольника, то в некоторых случаях
число областей будет максимальным.




А в некоторых нет! (Есть тройные пересечения)




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

Далее, вспоминая задачу о разбиении плоскости прямыми, я заново открыл такую картинку:



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

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

[Someone]

denny в сообщении #1403024 писал(а):

Этот результат находится по индукции, в полной аналогии с классической задачей о разбиении плоскости прямыми.

Можно, конечно, но можно и обойтись. $n\geqslant 3$ точек на окружности определяют выпуклый $n$-угольник. Вне его имеется $n$ частей. Предполагаем, что внутри этого многоугольника никакие три прямые не проходят через одну точку.
Число частей внутри можно подсчитать так. Рассмотрим выпуклый $n$-угольник. Пока ни одна диагональ не проведена, имеется одна часть. Далее проводим в нём диагонали. При проведении очередной диагонали, которая пересекается с $k$ ранее проведёнными диагоналями, она разбивается внутренними точками пересечения на $k+1$ частей, поэтому число частей, на которые разбит $n$-угольник всевозможными диагоналями, равно

$$1+\text{число внутренних точек пересечения}+\text{число диагоналей}.$$

Число внутренних точек пересечения равно числу четвёрок вершин, так как каждая четвёрка вершин даёт одну точку пересечения диагоналей соответствующего выпуклого четырёхугольника, и наоборот, каждая внутренняя точка пересечения диагоналей определяет четвёрку вершин выпуклого четырёхугольника, которые являются концами этих диагоналей. Поэтому число внутренних точек пересечения равно

$$C_n^4.$$

Число диагоналей, очевидно, равно

$$\text{число пар точек}-\text{число сторон}=C_n^2-n.$$

Поэтому число частей, на которые разбит круг, равно

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

Легко проверить непосредственной подстановкой, что при $0\leqslant n\leqslant 2$ формула тоже верна.

По поводу наименьшего числа частей ничего сказать не могу, кроме того, что, видимо, надо минимизировать число точек пересечения диагоналей внутри $n$-угольника.

-- Чт июл 04, 2019 00:47:39 --

denny в сообщении #1403024 писал(а):

Этот результат находится по индукции, в полной аналогии с классической задачей о разбиении плоскости прямыми.

Можно, конечно, но можно и обойтись. $n\geqslant 3$ точек на окружности определяют выпуклый $n$-угольник. Вне его имеется $n$ частей. Предполагаем, что внутри этого многоугольника никакие три прямые не проходят через одну точку.
Число частей внутри многоугольника можно подсчитать так. Рассмотрим выпуклый $n$-угольник. Пока ни одна диагональ не проведена, имеется одна часть. Далее проводим в нём диагонали. При проведении очередной диагонали, которая пересекается с $k$ ранее проведёнными диагоналями, она разбивается внутренними точками пересечения на $k+1$ частей, поэтому число частей, на которые разбит $n$-угольник всевозможными диагоналями, равно

$$1+\text{число внутренних точек пересечения}+\text{число диагоналей}.$$

Число внутренних точек пересечения равно числу четвёрок вершин, так как каждая четвёрка вершин даёт одну точку пересечения диагоналей соответствующего выпуклого четырёхугольника, и наоборот, каждая внутренняя точка пересечения диагоналей определяет четвёрку вершин выпуклого четырёхугольника, которые являются концами этих диагоналей. Поэтому число внутренних точек пересечения равно

$$C_n^4.$$

Число диагоналей, очевидно, равно

$$\text{число пар точек}-\text{число сторон}=C_n^2-n.$$

Поэтому число частей, на которые разбит круг, равно

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

Легко проверить непосредственной подстановкой, что при $0\leqslant n\leqslant 2$ формула тоже верна.

По поводу наименьшего числа частей ничего сказать не могу, кроме того, что, видимо, надо минимизировать число точек пересечения диагоналей внутри $n$-угольника.

[Mikhail_K]

(Оффтоп)

denny в сообщении #1403024 писал(а):

Педагогический смысл задачи в том, что для $n = 1, 2, 3, 4$ прямым подсчетом получается $A_n = 2^{n-1}$
А для $n=5 $ находим $31$, т.е. $2^{n-1} - 1$

Здесь опечатка. При $n=5$ тоже получается $2^{n-1}=16$, а вот при $n=6$ уже $2^{n-1}-1=31$.

[denny]

Mikhail_K

Да, спасибо. К сожалению, не получается отредактировать.

Someone

Спасибо за комбинаторное решение!