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

Правила

Есть три стержня. На один из них надета башня — стопка дисков разного размера, самый большой внизу, самый маленький вверху. Нужно перенести всю башню на другой стержень. Правила всего два^[1]:

1. За ход можно переложить только один диск — верхний.
2. Нельзя класть больший диск на меньший.

Сколько ходов нужно

Минимальное число ходов для n дисков — 2ⁿ − 1:

Каждый новый диск удваивает работу и добавляет ещё один ход.

Как решать: рекурсия

Решение красиво описывается через само себя. Чтобы перенести башню из n дисков со стержня А на стержень В:

1. Перенесите верхние n − 1 дисков на свободный стержень Б (это та же задача, только меньше).
2. Переложите самый большой диск на В.
3. Перенесите n − 1 дисков с Б на В.

Отсюда и формула: если для n − 1 дисков нужно T ходов, то для n — это T + 1 + T. Начиная с одного диска (1 ход), получаем 3, 7, 15, 31… — то есть 2ⁿ − 1.

Как решать без размышлений

Есть и простое циклическое правило. Пронумеруем стержни 1, 2, 3 (башня на первом). Ходы делают попарно между стержнями в постоянном порядке, каждый раз перекладывая меньший из двух верхних дисков:

• при чётном числе дисков: 1–2, 1–3, 2–3, и снова по кругу;
• при нечётном числе дисков: 1–3, 1–2, 3–2, и снова по кругу.

В паре стержней ход всегда один: меньший верхний диск перекладывается на другой стержень (или на пустой). Башня окажется на третьем стержне ровно за 2ⁿ − 1 ходов — мы проверили это правило перебором для 2–6 дисков.

Легенда о конце света

Головоломку придумал французский математик Эдуар Люка в 1883 году^[2]; её называют ещё «башней Брахмы». Её продавали как игрушку якобы от «профессора Клауса» — имя было анаграммой фамилии Люка. К игрушке прилагалась легенда: в храме города Бенарес монахи перекладывают 64 золотых диска между алмазными стержнями. Когда они закончат, башня и храм рассыплются в прах и наступит конец света.

Ещё одна головоломка с математикой внутри — пятнашки.