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

В этом разделе мы подробно расскажем Вам о головоломке под названием "Ханойская башня". 

История создания головоломки “Ханойская башня”

В 1883 году французский математик Эдуард Люка придумал известную игру под названием ханойская башня, Первоначально ее продавали как игрушку под названием "Профессор Клаусс" (Claus) из "Колледжа Ли-Су-Стьян" (Li-Sou-Stian), но вскоре обнаружилось, что профессор из несуществующего колледжа всего-навсего анаграмма фамилии изобретателя игры – профессора Люка (Lucas) из колледжа Сен-Луи (SaintLouis) [1]

image001.jpg

Задача состояла в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другую подставку по следующим правилам:

1. За один раз разрешается переносить только одно кольцо;

2. Нельзя класть большее кольцо на меньшее.

Эта задача довольно просто решается. Одно колечко можно переложить за один ход. Два колечка можно переложить за 3=1+1+1=4-1 ход – сначала перекладываем одно колечко за один ход, потом второе еще за один, и затем маленькое на большое еще за один. Для трех колечек сначала складываем пирамидку из двух меньших колечек на свободном стержне за три хода, как показано на предыдущем шаге, потом перекладываем большее кольцо на второй свободный стержень, а затем складываем на большом колечке пирамидку из двух более маленьких еще за три хода. В итоге общее количество ходов равно 3+1+3=7=8-1. Для четырех колечек количество ходов будет равно 7+1+7=15=16-1. Используя метод математической индукции можно показать, что для n колечек необходимо 

image003.png

перекладываний

image005.png

В первоначальном описании игра называется упрощенным вариантом мифической "Пирамиды браминов" в храме индийского города Бенареса. Эта пирамида состоит из 64 золотых колец, которые по сей день перекладывают жрецы храма. Как только им удастся справиться со своей задачей, храм рассыплется в пыль, грянет гром и мир исчезнет [2]. Ранее мы выяснили, что для того, чтобы переложить 64 кольца необходимо

image007.png

перекладываний. Даже если каждую секунду перекладывать по одному кольцу на выполнение этой работы у жрецов уйдет не менее 584942417355 лет.

Аналогичная головоломка встречается в книге Генри Э. Дьюдени "Кентерберийские головоломки", изданной впервые в 1907 году под названием "головоломка Мажордома": "Мажордом был хитрым и достаточно образованным человеком. По словам Чосера, "так овцам счет умел вести он, акрам и так подчистить свой амбар иль закром, что сборщики все оставались с носом. Он мог решать сложнейшие вопросы…" Поэт также отмечает, что "он никогда не попадал впросак". Всякого рода забавные задачи и причудливые идеи без труда возникали в его остром уме. В одной придорожной таверне, где остановились паломники, его бдительный взор обнаружил несколько кругов сыра разный величины. И вот, попросив четыре табурета, он предложил показать одну из своих головоломок, которая могла позабавить путников во время отдыха. Затем Мажордом положил на крайний табурет восемь кругов сыра (так что меньший лежит на большем, как кольца в пирамидке). Вот загадка, - воскликнул он, - которую я задал однажды своим приятелям из Болдсуэлла, что находятся в Норфолке, и, клянусь святым Иосифом, среди них не нашлось ни одного, кто осилил бы ее! Однако она очень проста, ибо все, что я хочу, так это, чтобы, перекладывая сыры с одного табурета на другой, вы перенесли все их на табурет, стоящий на другом конце, ни разу не положив какой-нибудь круг сыра на круг меньшего размера. Того, кто сумеет это сделать с наименьшим числом перекладываний, угощу глотком самого лучшего вина, какое только найдется у нашего доброго хозяина." [2] Как видите эта задача очень похожа на головоломку Эдуарда Люка, но теперь площадок для перекладывания уже четыре, а не три. Можно поставить также пять табуретов, шесть и больше, но начнем с четырех. Что изменилось в головоломке? Стало не так "тесно", как в головоломке с ханойской башней, а значит число перекладываний можно уменьшить, можно переложить сыры быстрее чем в ситуации с тремя табуретами. Однако, кроме "простора" появился еще и выбор: можно один и тот же набор сыров перекладывать разными способами, за разное число ходов. Так четыре сыра можно переложить следующими способами:

1. Переложить два меньших за три хода, потом два больших – за три хода, а затем положить меньшие на большие еще за три хода, в итоге получаем 3+3+3=9 перекладываний.

2. Переложить сначала три верхних сыра на одну табуретку, это можно сделать за 5 ходов (проверьте), затем переложить самый большой, а потом сверху на него выложить три меньших сыра еще за 5 ходов, в результате имеем 5+1+5=11 перекладываний.

Поэтому возникает естественный вопрос, какой способ перекладывания дает наименьшее число ходов. И это уже очень серьезная математическая задача. Только в работе 2014 года было доказано, что такой способ есть для четырех табуретов [3], однако для пяти и более табуретов такого доказательства на сегодняшний день нет. Есть гипотеза о том какой способ перекладывания будет оптимальным, но строго доказать, что это действительно так пока у математиков не получается.

Читать дальше

[1] Гарднер, М. Математические головоломки и развлечения / М. Гарднер, M.:Мир – 1971.

[2] Дьюдени, Г. Э. Кентерберийские головоломки / Г. Э. Дьюдени, M.:Мир – 1979.

[3] Bousch, T. La quatrieme tour de Hanoi Bull / Belg. Math. Soc. Simon Stevin, 2014(21), p. 895–912.