В обычной Ханойской башне три стержня. А что будет, если добавить ещё один, и их станет четыре? Правила те же: за раз двигают один диск, нельзя класть большой диск на маленький, а башню нужно перенести на другой стержень.
Всего один стержень — и ходов намного меньше
Появляется ещё одно место, куда можно убрать диски, и убирать их становится гораздо проще. Если сравнить минимальное число ходов, разница тем больше, чем больше дисков.
| Число дисков | Три стержня | Четыре стержня |
|---|---|---|
| 3 | 7 ходов | 5 ходов |
| 4 | 15 ходов | 9 ходов |
| 5 | 31 ход | 13 ходов |
| 6 | 63 хода | 17 ходов |
| 7 | 127 ходов | 25 ходов |
| 8 | 255 ходов | 33 хода |
| 10 | 1023 хода | 49 ходов |
| 64 | около 18,4 квинтиллиона ходов | 18 433 хода |
С тремя стержнями на перенос 64 дисков при одном ходе в секунду уйдёт около 585 млрд лет (Сколько лет понадобится на 64 диска?). А с четырьмя — 18 433 хода, то есть при одном ходе в секунду около 5 часов. Если бы легендарные монахи добавили один стержень, конец света наступил бы в тот же день.
«Головоломка с сырами» Дьюдени
Широко рассказал о Ханойской башне с четырьмя стержнями английский автор головоломок Генри Дьюдени. В книге «Кентерберийские головоломки» 1907 года он предложил её как «головоломку Рива». Рив — это управляющий поместьем.
В задаче Дьюдени вместо дисков — восемь сыров разного размера, и их нужно переносить между четырьмя табуретами. Класть большой сыр на маленький нельзя. Ответ — 33 хода, как и для 8 дисков в таблице выше.
Метод Фрейма — Стюарта
Способ переносить башню с четырьмя стержнями за малое число ходов в 1941 году независимо друг от друга опубликовали Дж. С. Фрейм и Б. М. Стюарт, и идея у них была одна. Чтобы перенести башню из n дисков, нужно разделить задачу на три части:
- Перенести верхние k дисков, используя все четыре стержня, на стержень, который не является целевым.
- Перенести оставшиеся n − k дисков на целевой стержень, используя только три стержня и не трогая стержень с верхними k дисками (2ⁿ⁻ᵏ − 1 ходов).
- Перенести k дисков, убранных на первом шаге, на целевой стержень, используя все четыре стержня.
Части 1 и 3 — это та же задача, только поменьше, поэтому можно применить рекурсию (статья об алгоритме). Остаётся выбрать, сколько дисков (k) оставить сверху, чтобы ходов было меньше всего. Для 8 дисков меньше всего ходов получается, если сначала убрать верхние 4 или 5 дисков, — 33 хода.
Почти сто лет без доказательства «минимума»
Стало известно, что методом Фрейма — Стюарта башню можно перенести за малое число ходов. Но нет ли способа ещё короче — это долгое время никто не мог доказать.
С тремя стержнями минимальное число ходов легко доказать из одного факта: «в момент, когда двигают самый большой диск, все остальные диски должны лежать на одном стержне» (статья о формуле минимального числа ходов). С четырьмя стержнями, когда двигают большой диск, остальные диски могут быть как угодно разложены по двум оставшимся стержням, и число возможных вариантов сразу резко растёт.
С помощью компьютера перебрали все расстановки и убедились, что для примерно 30 дисков этот метод даёт минимум. А в 2014 году, примерно через 100 лет после задачи Дьюдени, французский математик Тьерри Буш доказал, что метод Фрейма — Стюарта даёт минимум при любом числе дисков. Для пяти и более стержней, как считается, доказательства нет до сих пор.
Попробуйте сами
Ханойскую башню с четырьмя стержнями можно сделать из картона, как в статье о том, как её сделать, если нарисовать не три, а четыре кружка для мест. Попробуйте перенести 3 диска за 5 ходов, а 4 диска — за 9. Вы почувствуете разницу с тремя стержнями.
