Вы ищете первый крестик в цепочке и вы начинаете с первого возможного перемещения i = 1. Если есть возможность взятия в этом направлении, то вы регистрируете данные x, i в цепочке или таблице (во втором случае вы симулируете кучу). Вы выполняете взятие и начинаете сначала. Если же возможности взятия в данном направлении нет, то вы переходите к следующему i. Если вы достигаете четырех, то с этим крестиком все кончено, и вы переходите к следующему. Если их больше нет, то вы возвращаетесь к последней зарегистрированной в куче паре данных x, i, отменяете соответствующее взятие (изменение состояния игры) и продолжаете переходом к следующему i.

Вы уже проделали более трудную работу для самого длинного взятия в игре с курами и лисами.

Игра 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 x 24 = 86400 секунд, за год получаем 86400 x 365 — или порядка 3 x 107 секунд, откуда, наконец, 3 x 109 секунд за столетие. Поэтому нужно порядка 1015/3 x 109, или порядка 3 x 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)