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

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

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

Лемма

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

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

Доказательство. По делу а, три точки должны быть на одной линии: новая точка А, старая точка О к которой проводится линия, а точка я где пересекаются две старые линии. Есть п старые точки О, а значит, конечное число точек я где пересекаются две старые линии. Для каждого О и я, линия OI пересекает круг в одной точке, кроме О. Поскольку у круга бесконечно много точек, у него есть точка А который не будет ни в одной из строк OI. Тогда для этого момента А и все старые точки О, дело б будет правдой.

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

Решение

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

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

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

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

п − я − 1

точки слева и

я - 1 балл

справа, всего

(п − я − 1) (я − 1)

линии должны быть пересечены.

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

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

${ Displaystyle е (п) = е (п-1) + сумма _ {я = 1} ^ {п-1} влево (1+ влево (ни-1 вправо) влево (я-1 верно-верно)}$

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

${ Displaystyle е (п) = е (п-1) + сумма _ {я = 1} ^ {п-1} влево (2-п + н-я ^ {2} вправо)}$

используя суммы первого ${ Displaystyle (п-1)}$ натуральные числа и первые ${ Displaystyle (п-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 грани (двумерные ячейки), E ребра (одномерные ячейки) и V вершины (0-мерные клетки). Поскольку граф связан, соотношение Эйлера для двумерной сферы S ²

${ Displaystyle , В-Е + F = 2}$

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

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

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

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

${ Displaystyle V _ { text {интерьер}} = {п выбрать 4},}$

и так

${ displaystyle V = V _ { text {external}} + V _ { text {interior}} = n + {n choose 4}.}$

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

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

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

${ displaystyle 4 {п выбрать 4}}$

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

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

${ displaystyle 2 left ({n select 2} -n right)}$

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

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

${ 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.}$

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

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

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

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

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