В обычной Ханойской башне три стержня. А что будет, если добавить ещё один, и их станет четыре? Правила те же: за раз двигают один диск, нельзя класть большой диск на маленький, а башню нужно перенести на другой стержень.

Всего один стержень — и ходов намного меньше

Появляется ещё одно место, куда можно убрать диски, и убирать их становится гораздо проще. Если сравнить минимальное число ходов, разница тем больше, чем больше дисков.

Число дисковТри стержняЧетыре стержня
37 ходов5 ходов
415 ходов9 ходов
531 ход13 ходов
663 хода17 ходов
7127 ходов25 ходов
8255 ходов33 хода
101023 хода49 ходов
64около 18,4 квинтиллиона ходов18 433 хода

С тремя стержнями на перенос 64 дисков при одном ходе в секунду уйдёт около 585 млрд лет (Сколько лет понадобится на 64 диска?). А с четырьмя — 18 433 хода, то есть при одном ходе в секунду около 5 часов. Если бы легендарные монахи добавили один стержень, конец света наступил бы в тот же день.

«Головоломка с сырами» Дьюдени

Широко рассказал о Ханойской башне с четырьмя стержнями английский автор головоломок Генри Дьюдени. В книге «Кентерберийские головоломки» 1907 года он предложил её как «головоломку Рива». Рив — это управляющий поместьем.

В задаче Дьюдени вместо дисков — восемь сыров разного размера, и их нужно переносить между четырьмя табуретами. Класть большой сыр на маленький нельзя. Ответ — 33 хода, как и для 8 дисков в таблице выше.

Метод Фрейма — Стюарта

Способ переносить башню с четырьмя стержнями за малое число ходов в 1941 году независимо друг от друга опубликовали Дж. С. Фрейм и Б. М. Стюарт, и идея у них была одна. Чтобы перенести башню из n дисков, нужно разделить задачу на три части:

  1. Перенести верхние k дисков, используя все четыре стержня, на стержень, который не является целевым.
  2. Перенести оставшиеся n − k дисков на целевой стержень, используя только три стержня и не трогая стержень с верхними k дисками (2ⁿ⁻ᵏ − 1 ходов).
  3. Перенести k дисков, убранных на первом шаге, на целевой стержень, используя все четыре стержня.

Части 1 и 3 — это та же задача, только поменьше, поэтому можно применить рекурсию (статья об алгоритме). Остаётся выбрать, сколько дисков (k) оставить сверху, чтобы ходов было меньше всего. Для 8 дисков меньше всего ходов получается, если сначала убрать верхние 4 или 5 дисков, — 33 хода.

Почти сто лет без доказательства «минимума»

Стало известно, что методом Фрейма — Стюарта башню можно перенести за малое число ходов. Но нет ли способа ещё короче — это долгое время никто не мог доказать.

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

С помощью компьютера перебрали все расстановки и убедились, что для примерно 30 дисков этот метод даёт минимум. А в 2014 году, примерно через 100 лет после задачи Дьюдени, французский математик Тьерри Буш доказал, что метод Фрейма — Стюарта даёт минимум при любом числе дисков. Для пяти и более стержней, как считается, доказательства нет до сих пор.

Попробуйте сами

Ханойскую башню с четырьмя стержнями можно сделать из картона, как в статье о том, как её сделать, если нарисовать не три, а четыре кружка для мест. Попробуйте перенести 3 диска за 5 ходов, а 4 диска — за 9. Вы почувствуете разницу с тремя стержнями.