Разделение круга на области

В геометрии задача разделения круга на области с помощью вписанного многоугольника с n сторонами таким образом, чтобы максимизировать число площадей, создаваемых краями и диагоналями , иногда называемая , проблемой круга Мозера имеет решение индуктивный метод. Максимально возможное количество регионов, r _G = ${n \choose 4}+{n \choose 2}+1$ , давая последовательность 1, 2, 4, 8, 16, 31, 57, 99, 163 , 256, ... ( OEIS : A000127 ). Хотя первые пять членов соответствуют геометрической прогрессии 2 ^{п - 1}, оно отклоняется при n = 6 , показывая риск обобщения лишь на основе нескольких наблюдений.

Лемма

Если на окружности n точек и добавлена еще одна точка, n можно провести линий от новой точки к ранее существовавшим точкам. Возможны два случая. В первом случае ( а ) новая линия проходит через точку пересечения двух или более старых линий (между ранее существовавшими точками). Во втором случае ( b ) новая линия пересекает каждую из старых линий в разных точках. Будет полезно узнать следующий факт.

Лемма . Новую точку A можно выбрать так, чтобы случай b для каждой новой линии возникал .

Доказательство . В случае a три точки должны находиться на одной линии: новая точка A , старая точка O, к которой проводится линия, и точка I , где пересекаются две старые линии. Существует n старых точек O и, следовательно, конечное число точек I, в которых пересекаются две старые прямые. Для каждого O и I линия OI кроме O. пересекает круг в одной точке , Так как окружность имеет бесконечно много точек, то у нее есть точка А , которая не будет лежать ни на одной из прямых OI . Тогда для этой точки A и всех старых точек O случай b будет верен .

Эта лемма означает, что если существует k линий, пересекающих AO , то каждая из них пересекает AO в разных точках и k создает линия AO + 1 новых областей .

Решение

Индуктивный метод

Лемма устанавливает важное свойство для решения задачи. Используя индуктивное доказательство , можно прийти к формуле для f ( n ) через f ( n − 1).

На рисунке темные линии соединяют точки с 1 по 4, разделяя круг на 8 областей (т. е. f (4) = 8). показан индуктивный шаг от n = 4 до n На этом рисунке пунктирными линиями = 5. Когда добавляется пятая точка (т. е. при вычислении f (5) с использованием f (4)), это приводит к добавлению четырех новых линий (пунктирные линии на диаграмме), пронумерованных от 1 до 4, по одной для каждой точки, в которой они находятся. подключиться к. Таким образом, количество новых регионов, введенных пятой точкой, можно определить, учитывая количество регионов, добавленных каждой из 4 строк. Установите i для подсчета добавляемых строк. Каждая новая линия может пересекать несколько существующих линий, в зависимости от того, к какой точке она находится (значение i ). Новые линии никогда не будут пересекать друг друга, кроме как в новой точке.

Количество линий, которые пересекает каждая новая линия, можно определить, учитывая количество точек «слева» от линии и количество точек «справа» от линии. Поскольку между всеми существующими точками уже есть линии, количество точек слева, умноженное на количество точек справа, и будет количеством линий, которые будут пересекать новую линию. Для линии, ведущей к точке i , есть

п - я - 1

точки слева и

я - 1

точки справа, поэтому всего

( п - я - 1) ( я - 1)

линии должны пересекаться.

В этом примере каждая линия i = 1 и i = 4 пересекает нулевые линии,в то время как линии i = 2 и i = 3 пересекают две линии (есть дветочки с одной стороны и одну с другой).

Таким образом, повторяемость можно выразить как

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}).

Используя суммы первых $(n-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.

Комбинаторика и метод топологии

к н	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
Серия, альтернативно полученная из сумма до первых 5 слагаемых каждой строки треугольника Паскаля ^[1]

Лемма утверждает, что число областей максимально, если все «внутренние» пересечения хорд простые (через каждую точку пересечения внутри проходят ровно две хорды). Так будет, если точки на окружности выбраны « в общем положении ». общего пересечения» количество регионов также можно определить неиндуктивным способом, используя формулу для эйлеровой характеристики связного При этом предположении « плоского графа (рассматриваемого здесь как граф, вложенный в 2- сферу S ²).

Плоский граф определяет клеточное разложение плоскости с F гранями (2-мерные ячейки), E рёбрами (1-мерные ячейки) и V вершинами (0-мерные ячейки). Поскольку граф связен, соотношение Эйлера для двумерной сферы S ²

\,V-E+F=2

держит. Просмотрите диаграмму (круг вместе со всеми хордами) выше как плоский граф. общие формулы для V и E Если можно найти , то можно вывести и формулу для F , что решит проблему.

Его вершины включают в себя n точек окружности, называемые внешними вершинами, а также внутренние вершины, пересечения различных хорд внутри круга. Сделанное выше допущение «общего пересечения» гарантирует, что каждая внутренняя вершина является пересечением не более двух хорд.

Таким образом, основной задачей при определении V является нахождение количества внутренних вершин. Как следствие леммы, любые две пересекающиеся хорды однозначно определяют внутреннюю вершину. Эти хорды, в свою очередь, однозначно определяются четырьмя соответствующими конечными точками хорд, которые все являются внешними вершинами. Любые четыре внешние вершины определяют вписанный четырехугольник , а все вписанные четырехугольники являются выпуклыми четырехугольниками , поэтому каждый набор из четырех внешних вершин имеет ровно одну точку пересечения, образованную их диагоналями (хордами). Кроме того, по определению все внутренние вершины образованы пересекающимися хордами.

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

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

и так

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

Ребра включают в себя n дуг окружностей, соединяющих пары соседних внешних вершин, а также сегменты хордальных линий (описанные ниже), созданные внутри круга совокупностью хорд. Поскольку существует две группы вершин: внешние и внутренние, сегменты хордальных линий можно разделить на три группы:

Ребра напрямую (не пересекаемые другими хордами), соединяющие две внешние вершины. Это хорды между соседними внешними вершинами, образующие периметр многоугольника. Таких ребер n .
Ребра, соединяющие две внутренние вершины.
Ребра, соединяющие внутреннюю и внешнюю вершину.

Чтобы найти количество ребер в группах 2 и 3, рассмотрим каждую внутреннюю вершину, соединенную ровно с четырьмя ребрами. Это дает

4{n \choose 4}

края. Поскольку каждое ребро определяется двумя вершинами конечных точек, были пронумерованы только внутренние вершины, ребра группы 2 учитываются дважды, а ребра группы 3 учитываются только один раз.

Каждая хорда, разрезаемая другой (т. е. аккорды, не входящие в группу 1), должна содержать два ребра группы 3, ее начальный и конечный хордальные сегменты. Поскольку хорды однозначно определяются двумя внешними вершинами, то всего существует

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

группа 3 ребра. Это в два раза больше общего количества аккордов, которые сами не являются членами группы 1.

Сумма этих результатов, разделенная на два, дает общее количество ребер в группах 2 и 3. Сложение n ребер из группы 1 и 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 , $\,F=E-V+2,$ тогда получается

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

Поскольку одна из этих граней является внешней стороной круга, число областей 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

что дает тот же полином четвертой степени, полученный индуктивным методом

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

Пятый столбец треугольника Бернулли ( k = 4) дает максимальное количество областей в задаче разделения круга на области для n + 1 точек, где n ≥ 4.

Приложение к математическому бильярду внутри круга

При рассмотрении бессилового движения частицы внутри круга было показано (см. Д. Жо), что для определенных углов отражения вдоль границы круга соответствующая последовательность деления площади задается арифметической прогрессией.

См. также

Последовательность ленивого поставщика провизии - где n - количество прямых разрезов.

Ссылки

^ ОЭИС : A000127

Конвей, Дж. Х. и Гай, Р. К. «Сколько регионов». В «Книге чисел» . Нью-Йорк: Springer-Verlag, стр. 76–79, 1996.
Вайсштейн, Эрик В. «Деление круга по аккордам» . Математический мир .
http://www.arbelos.co.uk/Papers/Chords-regions.pdf. Архивировано 4 сентября 2011 г. в Wayback Machine.
Жод, Д. «Целочисленные последовательности из делений круга с помощью рациональных бильярдных траекторий». В «ICGG 2022 – Материалы 20-й Международной конференции по геометрии и графике», DOI: 10.1007/978-3-031-13588-0_8.

[1] ОЭИС : A000127

[1]