Задача о разрезании пиццы.
Сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом? Или в другой формулировке: каково максимальное число Ln областей, на которые плоскость делится n прямыми?
Новая n-я прямая (при n > 0) увеличивает число областей на к тогда и только тогда, когда рассекает k старых областей, а рассекает она к старых областей тогда и только тогда, когда пересекает прежние прямые в k—1 различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать n — 1 старых прямых не более чем в n— 1 различных точках, а значит k<=n и тогда Ln<= Ln-1+n. Более того, легко показать по индукции, что в этой формуле можно достичь равенства. Мы проводим n-ю прямую так, чтобы она не была параллельна никакой другой (следовательно, она пересекает каждую из них) и так, чтобы она не проходила ни через одну из имеющихся точек пересечения (следовательно, она пересекает каждую из прямых в различных местах). Поэтому рекуррентное соотношение имеет вид:
(1.2)
Теперь найдём прямую формулу. Угадать её здесь несколько сложнее (1,2,4,7, 11,16...), поэтому используем другой подход, основанный на развёртывании рекурентного соотношения:
Задача Иосифа Флавия.
Иосиф выжил и стал известным благодаря математической одаренности. В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. Однако Иосиф, наряду с одним из своих единомышленников, счел подобный конец бессмысленным — он быстро вычислил спасительные места в порочном круге, на которые поставил себя и своего товарища.
Для начала решим более упрощённый вариант этой задачи, в которой воинов будет n, а убивать будут каждого второго. Обозначим за J(n) номер последнего в подобном счёте.
Допустим, что первоначально имеется 2n людей. После первого прохода по кругу мы остаемся только с нечётными номерами и следующий проход начинается с номера 3:
Это все равно, как если
бы мы начинали с n людей,
за исключением того, что номер каждого
уцелевшего удваивается и уменьшается
на 1. Значит:
.
Ну, а как насчет нечетного случая? Оказывается, что в случае 2n + 1 людей жертва с номером 1 уничтожается сразу после жертвы с номером 2п, и мы остаемся с номерами
Опять получили почти
первоначальную ситуацию с n
людьми, но на этот раз номера уцелевших
удваиваются и увеличиваются на 1:
.
Объединяя эти рекуррентные соотношения, получаем:
(1.3)
Гипотеза:
при m>=0 и 0<=k
< 2m.
Как и прежде, мы будем использовать индукцию, но на этот раз —индукцию по m. При m=0
имеем k = 0; таким образом, база индукции сводится к равенству J(1) = 1, которое не вызывает сомнений. Индуктивный шаг состоит из двух частей в зависимости от того, четно или нечетно k.
Если m > 0 и 2m + k = 2n, то k четно и
(1.4)
Что и требовалось
доказать. Аналогичное доказательство
проходит и в нечетном случае, или можно
просто использовать тот факт, что
.
Теперь, когда самое трудное позади (решена задача), осмотримся немного: решение всякой задачи может быть обобщено так, что его можно применить к более широкому кругу задач.