Ханойская башня: красивая легенда и элегантный алгоритм. Как решить?

В XIX веке была очень популярна одна головоломка, которую придумал математик Франсуа Эдуард Анатоль Люка (François Édouard Anatole Lucas) из колледжа Сен-Луи (Saint Louis). Она была выполнена в форме игрушки и продавалась в качестве развлечения. И носила странное название «Профессор Claus из колледжа Li-Sou-Stian». Пытливые умы еще до решения задачи разгадали первую загадку еще в названии — это анаграмма, скрывающая настоящую фамилию создателя игры и названия колледжа: Lucas и Saint Louis.

Легенда

Игрушка состояла из 3 колышек, на одно из которых было нанизано несколько колечек — от большего к меньшему внизу наверх. Задача заключалась в том, чтобы перенести все колечки на другой колышек, но с несколькими условиями: за один ход можно перенести только одно колечко, сверху всегда должно быть колечко меньшего диаметра, нельзя откладывать кольца в сторону — только на промежуточный колышек. Как и у любой игры, у нее была легенда и красивое название — Ханойская башня.

Легенда заключалась в том, что в городе Ханой расположен храм бога Брамы. В нем находится плита с тремя стержнями из алмаза. При сотворении мира Брама нанизал на один стержень 64 золотых диска в форме пирамиды, и назвал это башней Брамы. Внизу лежал самый большой, а каждый следующий был все меньше и меньше. Если перенести все диски на другой стержень, соблюдая определенные условия, храм обратится в пыль, а мир — в небытие. А теперь, уважаемые знатоки, внимание, вопрос: через какое время наступит конец света, если жрецы будут беспрерывно переносить диски, скажем, по 1 в секунду?

Алгоритм

Эта задача — не просто забавная игра, а проверка интеллекта и функции мышления. Для ее решения есть несколько способов, мы рассмотрим алгоритм из 5 колец. Поняв его правила, мы сможем применить его к любому количеству колец и выяснить, когда же придет апокалипсис. Итак, у нас 3 правила:

• Один ход — одно кольцо
• Большее всегда ниже меньшего
• Не откладывать диски в сторону, только на другой стержень

У нас есть 3 стержня слева направо — A, B и C. На стержне A расположены кольца снизу вверх 1, 2, 3, 4 и 5. Простота решения заключается в том, чтобы перенести на соседний стержень всю пирамидку, кроме самого нижнего кольца:

1. Кольцо 5 переносим на стержень C
2. 4 — B
3. 5 — B
4. 3 — C
5. 5 — A
6. 4 — C
7. 5 — C
8. 2 — B
9. 5 — B
10. 4 — A
11. 5 — A
12. 3 — B
13. 5 — C
14. 4 — B
15. 5 — B

Здесь у нас оказывается пирамидка, кроме самого большого кольца, на втором стержне. Далее нам необходимо перенести основание — 1 на самый дальний стержень — C, и далее так же за 15 ходов перенести остальную пирамидку на этот стержень.

1. 1 — C
2. 5 — A
3. 4 — C
4. 5 — C
5. 3 — A
6. 5 — B
7. 4 — A
8. 5 — A
9. 2 — C
10. 5 — C
11. 4 — B
12. 5 — B
13. 3 — C
14. 5 — A
15. 4 — C
16. 5 — C

Таким образом, количество перемещений равно 2 в степени Х минус 1, где Х — число колец. Проверяем: 2 в пятой степени = 32, 32 – 1 = 31 ход! Получается, монахам в храме Брамы нужно сделать 2 в 64-й степени перекладываний и минус одно: 18 446 744 073 709 551 615. Если взять один ход за одну секунду, то это 18 квинтиллионов 446 квадриллионов 744 триллиона 73 миллиарда 709 миллионов 551 тысяча 615 секунд или 584,9 миллиарда лет.

Чтобы щелкать такие задачки как орешки, не забывайте регулярно тренировать мозг. Постоянные нагрузки держат его в тонусе, и это помогает не только решать головоломки, но и быть продуктивнее в любых делах!