Вы уже проделали более трудную работу для самого длинного взятия в игре с курами и лисами.
Игра 31.
Число ходов f(р) для переноса р дисков получается переносом сначала p − 1 дисков со стержня d на стержень 3 − а − d за f(р − 1) ход, затем из перемещения диска р, что требует в точности одного хода, а затем возвращения р − 1 дисков из запаса на стержень прибытия за f(р − 1) ход, откуда получаем:
f(р) = 2 * f(р − 1) + 1,
g(p) = f(p) + 1 = 2 * f(р − 1) + 2 = 2 * (f(p − 1) + 1) − 2 * g(р − 1).
По индукции g(р) = 2pg(0).
Так как f(0) = 0, g(0) = f(0) + 1 = 1, g(р) = 2p, то, наконец
f(р) = 2p − 1.
Для игры с 50 дисками нужно 250 − 1 ходов. Но 210 равно 1024, или порядка 103. Следовательно, 250 порядка 1015.
В часе 3600 секунд, в сутках 3600 × 24 = 86400 секунд, за год получаем 86400 × 365 — или порядка 3 × 107 секунд, откуда, наконец, 3 × 109 секунд за столетие. Поэтому нужно порядка 1015/3 × 109, или порядка 3 × 105 веков для игры с 50 дисками, которая, таким образом, требует около 300000 веков…
Вот другой способ доказывать свойство четности. Пусть диски обозначены их порядковыми номерами, начиная с первого — самого маленького, и нужно показать, что два диска с номерами одной четности никогда не попадают непосредственно один на другой.
Опыт показывает, что для первых значений n реализация игры Н(n, d, а) дает следующее;
— диски, попадающие в основание стержней d и а, имеют ту же четность, что и n,
— диски, попадающие в основание запасного стержня, имеют другую четность.
Предположим, что это свойство справедливо для n − 1. Для реализации Н(n, d, а) нужно выполнить сначала Н(n − 1, d, 3 − а − d). В течение этой операции диск n остается в основании начального стержня d и, следовательно, в основании диска d находится диск n и потому диск той же четности, что и n. Диски, которые при этом оказываются в основании стержня прибытия для процедуры Н(n − 1, d, 3 − а − d), имеют (по предположению индукции) ту же четность, что и n − 1. Но этот стержень прибытия является для игры Н(n, d, а) запасным стержнем, и, следовательно, в основании запасного стержня оказываются диски, имеющие ту же четность, что и n − 1. Наконец, запасной стержень для игры Н(n − 1, d, 3 − а − d) есть а, в основание которого попадают диски с четностью n − 2, следовательно, с четностью n.
Перемещение диска n со стержня d на стержень а помещает n в основание стержня а, так что при этом свойство четности для а подтверждается. Проверьте, что для стержней d и 3 − а − d оно также подтверждается. Для этого разложите Н (n, d, а) на 5 операций:
Н (n − 2, d, а) n и n − 1 на стержне d
Р (n − 1, d, 3 − а − d) n на d, n − 1 на 3 − а − d
Н (n − 2, а, 3 − а − d)
Р (n, d, а) n на а, n − 1 на 3 − а − d
Н (n − 2, 3 − a − d, d)