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

На странице представлен дизайн принципов: Перестановочные головоломки и Рекурсивные головоломки.
Головоломка: Ханойская башня
Автор дизайна:
Эдуард Лукас

Игра под названием «Ханойская башня» была придумана французским математиком Эдуардом Лукасом в 1883 году и с тех пор является одновременно и популярной головоломкой, и известной математической задачей, которая является прекрасной иллюстрацией общей концепции рекурсии. Эта головоломка известна большинству математиков и очень большому количеству людей, которым нравятся либо головоломки, либо элементарные математические задачи.

Если вы не знакомы с этой концепцией, она очень проста: у вас есть база с тремя стержнями и определенным количеством дисков (количество дисков варьируется, а вместе с ним и сложность); Исходной позицией может быть любой из трех стержней. 

Цель состоит в том, чтобы переместить все диски на один из двух других стержней, соблюдая простой набор правил: 

  • вы можете перемещать только один диск за раз
  • нельзя ставить диск поверх меньшего. 

Задача Ханойской башни проста и ее очень легко решить, если вы начнете с нескольких дисков, но с каждым дополнительным диском уровень сложности возрастает экспоненциально. Для расчета количества ходов достаточно применить простую формулу -  2 n  - 1, где n — количество дисков. Поскольку эта версия имеет 8 дисков, минимальное количество ходов составляет 255, что уже довольно сложно, но все же не самое сложное.

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

Есть красивая легенда, что головоломка является упрощенным вариантом мифической «Пирамиды браминов» в храме индийского города Бенареса.

Как гласит предание, эта пирамида состоит из 64 золотых колец, которые и по сей день перекладывают жрецы храма. Как только им удастся справиться со своей задачей, храм рассыплется в пыль, грянет гром и мир исчезнет. О конце мира еще, пожалуй, можно спорить, но то, что храм за это время обратится в пыль, несомненно. Формула 264 - 1 дает двадцатизначное число 18446 744 073 703551 615. если бы жрецы работали не покладая рук, днем и ночью, перенося каждую секунду по одному кольцу, чтобы закончить работу, им понадобились бы многие миллионы тысячелетий.

Другие дизайны