Пункт 10

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

Условие

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

Решение

Заметим, что: (L_0)=1,(L_1)=2,(L_2)=4,…

Можем предположить: (L_n)=2^n

Но это не так: (L_3)=7

Заметим, что (L_n)≤(L_n-1)+n, так как новая прямая может пересекать не более, чем n-1 прямую. Тогда, можно предположить: (L_n)=(L_n-1)+n

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

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