Последовательность ленивого поставщика провизии

Блин разрезать на семь частей тремя прямыми разрезами.

Последовательность ленивого поставщика провизии, более формально известная как центральные многоугольные числа , описывает максимальное количество кусков диска ( для блин или пицца описания ситуации обычно используется ), которые можно сделать с помощью заданного количества прямых разрезов. Например, из трех разрезов блина получится шесть частей, если все разрезы встречаются в одной точке внутри круга, и до семи, если это не так. Эту задачу можно формализовать математически как подсчет ячеек в рядах ; обобщения на более высокие измерения см . в разделе «Расположение гиперплоскостей» .

Аналогом этой последовательности в трех измерениях являются номера тортов .

Формула и последовательность

Максимальное количество p деталей, которое можно создать с заданным количеством разрезов $n$ (где $n \geq 0$ ), определяется формулой

p={\frac {n^{2}+n+2}{2}}.

Используя биномиальные коэффициенты , формулу можно выразить как

p=1+{\dbinom {n+1}{2}}={\dbinom {n}{0}}+{\dbinom {n}{1}}+{\dbinom {n}{2}}.

Проще говоря, каждое число равно треугольному числу плюс 1. Это первое число в каждой строке треугольника Флойда .

Поскольку третий столбец треугольника Бернулли ( k = 2) представляет собой треугольное число плюс один, он образует последовательность ленивого поставщика провизии для n разрезов, где n ≥ 2.

Альтернативно последовательность может быть получена из суммы до первых трех членов каждой строки треугольника Паскаля : ^[1]

к н	0	1	2	Сумма
0	1	-	-	1
1	1	1	-	2
2	1	2	1	4
3	1	3	3	7
4	1	4	6	11
5	1	5	10	16
6	1	6	15	22
7	1	7	21	29
8	1	8	28	37
9	1	9	36	46

Эта последовательность (последовательность A000124 в OEIS ), начиная с $n = 0$ , приводит, таким образом, к

1 , 2 , 4 , 7 , 11 , 16 , 22 , 29 , 37 , 46 , 56 , 67 , 79 , 92 , 106 , 121 , 137 , 154 , 172 , 191 , 211 , ...

Его трехмерный аналог известен как числа тортов . Разница между последовательными номерами тортов дает последовательность ленивого поставщика провизии. ^[2]

Доказательство

Когда круг разрезается $n$ раз для получения максимального количества частей, представленного как $p = f (n)$ , $n-$ необходимо учитывать й разрез; количество частей перед последним разрезом равно $f (n - 1)$ , а количество частей, добавленных последним разрезом, равно $n$ .

Чтобы получить максимальное количество деталей, $n-$ я линия разреза должна пересекать все остальные предыдущие линии разреза внутри круга, но не пересекать ни одного пересечения предыдущих линий разреза. Таким образом, $сама n-$ я линия разрезается в $n - 1$ местах и на $n$ отрезков. Каждый отрезок делит один кусок $(n - 1)$ -разрезанного блина на 2 части, добавляя $ровно n$ к числу кусков . Новая линия не может иметь больше сегментов, поскольку она может пересекать каждую предыдущую линию только один раз. Линия разреза всегда может пересекать все предыдущие линии разреза, поскольку вращение ножа под небольшим углом вокруг точки, которая не является существующим пересечением, будет, если угол достаточно мал, пересечь все предыдущие линии, включая последнюю добавленную.

Таким образом, общее количество кусков после $n$ разрезов равно

f(n)=n+f(n-1).

Это рекуррентное соотношение можно решить. Если $f (n - 1)$ расширить на один член, отношение принимает вид

f(n)=n+(n-1)+f(n-2).

Расширение члена $f (n - 2)$ может продолжаться до тех пор, пока последний член не сократится до $f (0)$ , таким образом,

f(n)=n+(n-1)+(n-2)+\cdots +1+f(0).

Поскольку $f (0) = 1$ и до того, как будут сделаны какие-либо разрезы, есть один кусок, это можно переписать как

f(n)=1+(1+2+3+\cdots +n).

Это можно упростить, используя формулу суммы арифметической прогрессии :

f(n)=1+{\frac {n(n+1)}{2}}={\frac {n^{2}+n+2}{2}}.

См. также

Номер торта
Треугольник Флойда
Деление круга на области – где n – количество сторон вписанного многоугольника.

Примечания

^ ОЭИС : A000124
^ Яглом, А.М. ; Яглом, И.М. (1987). Сложные математические задачи с элементарными решениями . Том. 1. Нью-Йорк: Dover Publications .

Ссылки

Мур, Т.Л. (1991), «Использование формулы Эйлера для решения проблем разделения плоскостей», The College Mathematics Journal , 22 (2), Mathematical Association of America: 125–130, doi : 10.2307/2686448 , JSTOR 2686448 .

Штайнер, Дж. (1826), «Несколько заявлений о разделении плоскости и пространства»», Дж. Рейн Ангью. Математика , 1 : 349–364 .

Ветцель, Дж. Э. (1978), «О разделении плоскости линиями» (PDF) , American Mathematical Monthly , 85 (8), Mathematical Association of America: 647–656, doi : 10.2307/2320333 , JSTOR 2320333 , заархивировано из оригинал (PDF) от 21 июля 2011 г. , получен 15 декабря 2008 г.

Внешние ссылки

Вайсштейн, Эрик В. «Деление круга линиями» . Математический мир .

[1] ОЭИС : A000124

[2] Яглом, А.М. ; Яглом, И.М. (1987). Сложные математические задачи с элементарными решениями . Том. 1. Нью-Йорк: Dover Publications .

[1]

[2]