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

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

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

• 1 Лемма
• 2 Решение
  • 2.1 Индуктивный метод
  • 2.2 Комбинаторика и метод топологии
• 3 См. Также
• 4 Ссылки

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

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

Доказательство . Для случая a три точки должны находиться на одной линии: новая точка A, старая точка O, к которой проводится линия, и точка I, где пересекаются две старые линии. Есть n старых точек O и, следовательно, конечное число точек I, где пересекаются две старые прямые. Для каждого O и I линия OI пересекает окружность в одной точке, отличной от 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, имеется

n - i - 1

точек слева и

i - 1 точка

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

(n - i - 1) (i - 1)

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

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

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

$f\; (n)\; =\; f\; (n\; -\; 1)\; +\; \sum \; i\; =\; 1\; n\; -\; 1\; (1\; +\; (n\; -\; i\; -\; 1)\; (i\; -\; 1))\; \{\backslash \; Displaystyle\; е\; (п)\; =\; е\; (п-1)\; +\; \backslash \; сумма\; \_\; \{я\; =\; 1\}\; ^\; \{п-1\}\; \backslash \; влево\; (1+\; \backslash \; влево\; (ни-1\; \backslash \; вправо)\; \backslash \; влево\; (я-1\; \backslash \; right)\; \backslash \; right)\}$

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

$f\; (n)\; =\; f\; (n\; -\; 1)\; +\; \sum \; i\; =\; 1\; n\; -\; 1\; (2\; -\; n\; +\; ni\; -\; i\; 2)\; \{\backslash \; displaystyle\; f\; (n)\; =\; f\; (n-1)\; +\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{n-1\}\; \backslash \; left\; (2-n\; +\; ni-i\; ^\; \{2\}\; \backslash \; right)\}$

с помощью суммы первых $(n\; -\; 1)\; \{\backslash \; displaystyle\; (n-1)\}$натуральных чисел и первого $(n\; -\; 1)\; \{\backslash \; displaystyle\; (n-1)\}$квадратов, это объединяется в

$f\; (n)\; =\; f\; (n\; -\; 1)\; +\; 1\; 6\; n\; 3\; -\; n\; 2\; +\; 17\; 6\; n\; -\; 2\; \{\backslash \; displaystyle\; f\; (n)\; =\; f\; (n-\; 1)\; +\; \{\backslash \; frac\; \{1\}\; \{6\}\}\; n\; ^\; \{3\}\; -n\; ^\; \{2\}\; +\; \{\backslash \; frac\; \{17\}\; \{6\}\}\; n-2\}$

Наконец,

$f\; (n)\; Знак\; равно\; \sum \; К\; знак\; равно\; 1\; N\; (1\; 6\; К\; 3\; -\; К\; 2\; +\; 17\; 6\; К\; -\; 2)\; +\; 1\; \{\backslash \; displaystyle\; f\; (n)\; =\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; \backslash \; left\; (\{\backslash \; frac\; \{\; 1\}\; \{6\}\}\; k\; ^\; \{3\}\; -k\; ^\; \{2\}\; +\; \{\backslash \; frac\; \{17\}\; \{6\}\}\; k-2\; \backslash \; right)\; +1\}$с $f\; (0)\; =\; 1\; \{\backslash \; displaystyle\; f\; (0)\; =\; 1\}$

, что дает

$f\; (n)\; =\; n\; 24\; (n\; 3\; -\; 6\; n\; 2\; +\; 23\; n\; -\; 18)\; +\; 1\; \{\backslash \; display\; style\; f\; (n)\; =\; \{\backslash \; frac\; \{n\}\; \{24\}\}\; (n\; ^\; \{3\}\; -6n\; ^\; \{2\}\; +\; 23n-18)\; +1\}$

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

kn		0	1	2	3	4		Sum
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).

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

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

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

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

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

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

$V\; inner\; =\; (n\; 4),\; \{\backslash \; displaystyle\; V\; \_\; \{\backslash \; text\; \{inner\; \}\}\; =\; \{n\; \backslash \; choose\; 4\},\}$

и поэтому

$V\; =\; V\; external\; +\; V\; internal\; =\; n\; +\; (n\; 4).\; \{\backslash \; displaystyle\; V\; =\; V\; \_\; \{\backslash \; text\; \{external\}\}\; +\; V\; \_\; \{\backslash \; text\; \{inner\}\}\; =\; n\; +\; \{n\; \backslash \; choose\; 4\}.\}$

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

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

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

$4\; (n\; 4)\; \{\backslash \; displaystyle\; 4\; \{n\; \backslash \; choose\; 4\}\}$

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

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

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

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

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

$E\; =\; 4\; (n\; 4)\; +\; 2\; ((n\; 2)\; -\; n)\; 2\; +\; n\; +\; n\; =\; 2\; (n\; 4)\; +\; (n\; 2)\; +\; n.\; \{\backslash \; displaystyle\; E\; =\; \{\backslash \; frac\; \{4\; \{n\; \backslash \; choose\; 4\}\; +2\; \backslash \; left\; (\{n\; \backslash \; choose\; 2\}\; -n\; \backslash \; right)\}\; \{2\}\}\; +\; n\; +\; n\; =\; 2\; \{n\; \backslash \; choose\; 4\}\; +\; \{n\; \backslash \; choose\; 2\}\; +\; n.\}$

Подставив V и E в соотношение Эйлера, вычисленное для F, $F\; =\; E\; -\; V\; +\; 2,\; \{\backslash \; displaystyle\; \backslash ,\; F\; =\; E-V\; +\; 2,\}$тогда получается

$F\; =\; (n\; 4)\; +\; (n\; 2)\; +\; 2.\; \{\backslash \; displaystyle\; F\; =\; \{n\; \backslash \; choose\; 4\}\; +\; \{n\; \backslash \; choose\; 2\}\; +2.\}$

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

$r\; G\; =\; (n\; 4)\; +\; (n\; 2)\; +\; 1,\; \{\backslash \; displaystyle\; r\_\; \{G\}\; =\; \{n\; \backslash \; choose\; 4\}\; +\; \{n\; \backslash \; choose\; 2\}\; +1,\}$

, что преобразуется в

$r\; G\; =\; n!\; (п\; -\; 4)!\; 4!\; +\; п!\; (п\; -\; 2)!\; 2!\; +\; 1\; \{\backslash \; displaystyle\; r\_\; \{G\}\; =\; \{\backslash \; frac\; \{n!\}\; \{(N-4)!\; 4!\}\}\; +\; \{\backslash \; Frac\; \{n!\}\; \{(N-2)!\; 2!\}\}\; +\; 1\}$

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

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

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

1. ^OEIS : A000127

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