Разделение круга на области - Dividing a circle into areas

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

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

Лемма

Лемма

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

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

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

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

Решение

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

Лемма устанавливает важное свойство для решения задачи. Используя индуктивное доказательство , можно прийти к формуле для 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 пересекают две прямые (две точки с одной стороны и одна с другой).

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

который легко сводится к

используя суммы первых натуральных чисел и первых квадратов, получается

Наконец-то

с участием

который дает

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

k
п
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 членов
каждой строки треугольника Паскаля.

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

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

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

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

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

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

так что

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

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

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

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

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

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

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

Подставляя V и E в уравнение Эйлера, решенное для F , получаем

Поскольку одна из этих граней является внешней стороной круга, количество областей r G внутри круга равно F - 1, или

который решает

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

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

использованная литература

  • Конвей, Дж. Х. и Гай, РК «Сколько регионов». В Книге Чисел . Нью-Йорк: Springer-Verlag, стр. 76–79, 1996.
  • Вайштайн, Эрик В. «Деление круга по аккордам» . MathWorld .
  • http://www.arbelos.co.uk/Papers/Chords-regions.pdf