Европа · том III; игра выпущена в 1883 году
Ханойская башня
Как звучало тогда
В великом храме Бенареса под куполом, отмечающим середину мира, покоится бронзовый диск с тремя алмазными иглами. При сотворении мира бог надел на одну из них шестьдесят четыре диска чистого золота. Днём и ночью жрецы перекладывают диски, и, когда все шестьдесят четыре окажутся на другой игле, башня и храм рассыплются в прах, и с громовым раскатом мир исчезнет.
Условие
Перенести башню из $n$ дисков с одного стержня на другой, перекладывая по одному и никогда не кладя больший диск на меньший. Каково наименьшее число перекладываний? Сколько времени займут 64 диска при одном перекладывании в секунду?
Показать ответ
$2^n-1$; для 64 дисков это $18\,446\,744\,073\,709\,551\,615$ ходов, или около 585 миллиардов лет
О чём эта задача
Рекуррентное соотношение видно сразу: чтобы перенести $n$ дисков, надо перенести верхние $n-1$ на запасной стержень, переложить нижний и вернуть остальные, — значит $a_n=2a_{n-1}+1$. Отсюда $a_n=2^n-1$, и это школьная сумма геометрической прогрессии. Легенду про Бенарес Люка сочинил сам и выпустил игру под именем «профессора Клауса из Сиамского института» — анаграмма его собственной фамилии и Сен-Луи, лицея, где он преподавал. Возраст Вселенной — около 14 миллиардов лет, так что запас у жрецов изрядный.
Разбор — «как решали тогда» и «как решают сейчас» — для этой задачи ещё не написан.