Пункт 10

Задача о нарезании пиццы

Условие

Сколько максимум кусков пиццы можно получить, делая n n разрезов? Другими словами: найти число областей Ln L sub n, на которые плоскость разбивается n n прямыми.

Решение

Заметим, что: L0=1,L1=2,L2=4,… L sub 0 equals 1 comma L sub 1 equals 2 comma L sub 2 equals 4 comma dot dot dot

Можем предположить: Ln=2n L sub n equals 2 to the n-th power

Но это не так: L3=7 L sub 3 equals 7

Заметим, что Ln≤Ln-1+n L sub n is less than or equal to L sub n minus 1 plus n, так как новая прямая может пересекать не более, чем n-1 n minus 1 прямую. Тогда, можно предположить: Ln=Ln-1+n L sub n equals L sub n minus 1 plus n

Попробуем доказать это по индукции: пусть у нас есть n n прямых, которые делят плоскость на Ln L sub n кусков. Тогда, можно провести еще одну прямую, которая пересекает все эти прямые, и так получить максимальное количество частей. Соответственно, от такого у нас добавится n+1 n plus 1 областей. Итого, доказано, что: Ln=Ln - 1+n L sub n equals L sub n minus 1 plus n

Задача Иосифа Флавия