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

Задача по геометрии

Количество точек ( n ), хорд ( c ) и областей ( r _G ) для первых 6 членов задачи круга Мозера

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

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

${\displaystyle f(n)=f(n-1)+\sum _{i=1}^{n-1}{\big (}1+(n-i-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 - сферу S ² ).

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

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

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

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

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

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

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

и так

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle r_{G}}$(фиолетовый) и другие последовательности OEIS в треугольнике Бернулли.

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

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

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

Смотрите также

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

Рекомендации

1. ОЭИС : 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.