Ханойская башня

Сосчитайте ходы для небольшого числа колец — сначала одного, потом двух и трёх.

Пусть в башне k колец. Сколько ходов нужно сделать перед тем, как удастся сдвинуть со своего места самое нижнее кольцо на стержень B? А сколько потом ходов нужно будет сделать перед тем, как его удастся сдвинуть с B на C?

Начнём с обозначений. Пусть H(k) — наименьшее число ходов, за которое удаётся решить нашу задачу для переноса k колец. Если вы воспользовались советом из первой подсказки, то уже знаете, что H(1) = 2, H(2) = 8, а возможно, сумели аккуратно сосчитать и H(3) = 26.

А теперь давайте ответим на вопросы, заданные в подсказке 2. Перед переносом нижнего (k-го) кольца с него нужно снять всю верхнюю часть башни из (k – 1) кольца. Для этого нам потребуется H(k – 1) ходов, и никак не меньше. В результате все эти кольца окажутся на стержне C, что и даст возможность перенести нижнее кольцо с A на B (за 1 ход). После этого, увы, придётся всё ранее сделанное повторить в обратную сторону: чтобы освободить для нижнего кольца стержень C, мы должны с него всю верхнюю часть башни убрать на стержень A. Это требует еще H(k – 1) ходов. Затем (за 1 ход) переносим нижнее кольцо с B на C, и еще раз повторяем H(k – 1) ход для того, чтобы собрать верхнюю часть на стержне C заново. Итого нам потребовалось три раза по H(k – 1) и еще два отдельных хода. Могли ли мы получить результат быстрее? Нет. А медленнее? Как это ни удивительно — тоже нет, разве что мы бы в какой-то момент вернули обратно тот ход, который сделали только что.

Какой промежуточный итог у нас получился? А вот какой:

H(k) = 3H(k – 1) + 2.

Такие соотношения, в которых следующий член последовательности линейно (то есть с помощью линейной функции) выражен через предыдущий (один или несколько), называются линейными рекуррентами. Самый простой пример — способ задания арифметической прогрессии: a_k+1 = a_k + d. Чуть более сложный (но тоже очень известный) пример — числа Фибоначчи: f_k+2 = f_k+1 + f_k.

Что делать дальше? Ведь не применять же общие формулы — это как стрельба из пушек по воробьям.

Для восьми колец можно просто сосчитать ответ «в лоб» последовательными вычислениями по приведенной выше рекуррентной формуле. Он окажется равным 6560. Однако есть способ красивее.

Прибавим к H единичку: H'(k) = H(k) + 1. Тогда для H'(k) справедлива такая формула:

H'(k) = H(k) + 1 = 3H(k – 1) + 3 = 3H'(k – 1).

Следовательно, H'(k) — геометрическая прогрессия со знаменателем 3. Так как при этом H'(1) = 2 + 1 = 3, то H'(k) = 3^k, откуда

H(k) = 3^k – 1.

Обратите внимание, что в ответе получается формула, очень похожая на формулу для числа ходов в классической головоломке о ханойской башне, только у нас вместо 2 стоит 3. Это не случайно — и причины этой неслучайности будут объяснены чуть ниже.

Еще одно замечательное следствие из полученного нами результата состоит в том, что в процессе перекладывания колец встретятся все допустимые расположения колец на трёх стержнях, так сказать, «все позиции». Почему это можно утверждать? Потому, что общее число позиций равно 3^k (чтобы задать позицию, мы для каждого из k колец должны выбрать тот из трёх стержней, на котором оно в этой позиции находится — а порядок колец на стержне жёстко задан их размерами), и по той простой причине, что никакая позиция не встречается в процессе перекладывания дважды (иначе процесс можно было бы сократить). А поскольку мы вынуждены делать именно (3^k – 1) ходов, каждый раз получая неповторяющиеся позиции, то все позиции будут получены.

А теперь — небольшой экскурс в историю.

Как я честно написал в условии, головоломка «Ханойская башня» в дополнительной рекламе не нуждается. Тем не менее, история ее появления на свет не слишком широко известна.

В одном из храмов индийского города Бенареса установлена бронзовая плита с тремя алмазными стержнями. При сотворении мира верховный индуистский бог Брахма поместил на первый стержень 64 диска из чистого золота, в порядке уменьшения их размеров, и велел монахам переместить их на третий стержень, запретив при этом за один раз переносить более одного диска и помещать больший диск на меньший. С тех пор монахи день и ночь, сменяя друг друга, трудятся над этой задачей. Как только задача будет решена, храм рассыплется в прах и завершится жизнь Брахмы. Затем родится новый Брахма, и всё повторится...

Да, пока вы не успели поверить в то, что монахи индуистского монастыря действительно занимаются решением этой головоломки, спешу сообщить, что это всего лишь легенда. Причем вовсе не древняя, как большинство известных легенд. Придумал ее в конце XIX века французский математик Эдуард Люка. Красивая история оказалась очень удачным рекламным трюком для «раскрутки» (как сказали бы современные PR-менеджеры) придуманной Люка изящной головоломки, выполненной из дерева и состоящей из восьми дисков. Начиная с 1883 года она продавалась под разными названиями — «Башни Брахмы»,«Головоломка о конце света», «Пагода-головоломка», да и место действия легенды неоднократно переносилось то в Китай, то в Тибет, но в итоге «прижилось» во Вьетнаме  — вместе с названием «Ханойские башни».

Чтобы самому порешать головоломку, совсем не нужно покупать ее в магазине или скачивать компьютерную версию из Интернета. Для маленьких детей идеально подойдёт набор детских формочек:

Рис. 2

Впрочем, с помощью взрослых головоломку можно изготовить и из самых неожиданных «деталей»:

Рис. 3

Впрочем, вернёмся к математической части задачи. В ней было показано, что путь от исходного (все кольца собраны на левом стержне) до конечного (все кольца собраны на правом из трех стержней) состояния проходит абсолютно через все допустимые позиции. Нам осталось только осмыслить, как именно это происходит. Для этого давайте изобразим все возможные позиции игры в виде графа:

Рис. 4

На рис. 4 показаны графы H₁–H₄ башен с числом колец от 1 до 4. Ходы по сторонам самых маленьких треугольничков соответствуют переносу самого маленького кольца, ходы между такими треугольниками (но внутри треугольника следующего размера) — переносу следующего кольца, и т. д. Это в стандартной головоломке, когда все переносы разрешены. А что получается в нашей версии, когда между стержнями A и С ничего переносить нельзя?

Картинка с изображением графа, который получается из H₃, приведена на рис. 5:

Рис. 5

Попробуем понять, почему граф «обрезается» именно так, как показано на этой картинке. Для этого «укрупним» изображения точек на исходном графе и поместим на них информацию о том, какому расположению колец соответствует данная точка (рис. 6):

Рис. 6

Здесь «cbb», например, означает, что самое маленькое кольцо находится на стержне C, а оба остальных — на стержне B. При этом можно либо перенести маленькое кольцо (в стандартном графе — на любой из стержней A или B, то есть получить abb или bbb), либо перенести следующее кольцо на свободный стержень (то есть получить cab). В нашей версии переносы с A на C и с C на A запрещены, так что ровно один из этих трех ходов оказывается невозможным, — а это означает, что каждая позиция, кроме первой и последней, имеет ровно две соседних. Тем самым весь путь по графу оказывается одной длинной ломаной линией без всяких ответвлений. Собственно, именно об этом и была наша задача.

Интересно, что построенный нами путь по графу (точнее, его буквенная запись вида aaa – baa – ... – ccc) встречается в очень многих серьезных математических (и не только математических) исследованиях и носит специальное название — код Грея. Главная особенность кодов Грея состоит в том, что соседние значения в последовательности «кодовых слов» отличаются только в одном разряде.

Основное предназначение кодов Грея в наше время — защита информации от помех и ошибок при передаче по каналам связи. Используют коды и разработчики электронных устройств. Например, в статье о графических планшетах рассказано, как это делалось в 1960-е годы в графических устройствах фирмы RAND. Забавно, что изобретателем графического планшета считают Элишу Грея — а «отец» кода Фрэнк Грей, судя по всему, даже не родственник Элише, а всего лишь однофамилец.

Впрочем, у этих кодов есть и более забавные применения. Представьте себе, что вы пытаетесь подобрать ключ к кодовому замку (например, на вокзальной камере хранения или на ремне, которым вы прошлым летом привязали свой велосипед к стенке сарая; рис. 7). Если перебирать все коды по порядку, то в процессе перебора нередко придётся крутить замок слишком долго. Например, для перехода от 999 к 1000 нужно вращать все четыре разрядных колёсика.

Рис. 7

Однако если вы пользуетесь для подбора «секрета» кодом Грея (только не двоичным, который описан в статье Википедии по ссылке, и не троичным, который выше построили мы, а десятичным!), то перебор в режиме «один маленький поворот в секунду» займёт у вас ровно столько времени, сколько всего есть кодов, потому что каждый следующий код будет получаться из предыдущего ровно одним поворотом. То естьвсего 9999 секунд. Это, конечно, всё равно около трех часов, но всё-таки не так долго, как при стандартном переборе.

Кстати, о времени. Если в классической легенде Люка о башне Брахмы и «конце света» наступление конца света ожидается после (2⁶⁴ – 1) ходов, то в нашей версии головоломки монахам бы потребовалось (3⁶⁴ – 1) ходов. Попробуйте мысленно предположить, во сколько раз это больше. Хотя бы по порядку величины — в 100? В 1000? В 10 000? Я уверен, что правильный порядок не угадает почти никто. Наш ответ больше классического более чем в 10¹¹ раз.

И раз мы уже затронули тему времени, не могу не упомянуть в этой связи замечательный рассказ Эрика Фрэнка Рассела «Игра на выживание». В нем жестокие инопланетяне-гомбарийцы обрекают главного героя-землянина на казнь, но их обычай разрешает ему перед казнью сыграть в любую настольную игру. Результат поединка ничего не решает, но пока игра не закончится, пленник будет жить. Как вы думаете, какую игру выбирает герой?