Ханойские башни
Эта головоломка известна уже довольно давно. Её автором принято считать французского математика Э. Люка, создавшего ее на основе древних легенд. В русской литературе она впервые появилась, видимо, в 1902 году в книге Е. Игнатьева «В царстве смекалки». Об этой книге мы недавно рассказывали в нашем журнале («Квант» № 4, 1991 г.). Многие авторы книг по программированию, очарованные простотой и изяществом «ханойской башни», описывали алгоритм ее решения.
Что же представляет из себя эта головоломка, которую иногда именуют «Башней браминов», а Е. Игнатьев называет «Детской пирамидкой»? Если вы возьмете детскую пирамиду (диски располагаются в порядке возрастания: верхний — самый маленький, а нижний — самый большой) и еще два стержня от таких же детских пирамид, то головоломка уже у вас в руках.
Занумеруем стержни: тот, на котором находятся диски, получит номер 1, другие — номера 2 и 3. Задача состоит в том, чтобы перенести диски со стержня 1 на стержень 3, используя стержень 2, как промежуточный. При этом должны соблюдаться два условия:
- за один ход можно переносить лишь один диск,
- нельзя класть больший диск на меньший.
Существует легенда, что в индийском городе Бенаресе бог Брама поставил в одном из храмов на бронзовой площадке три алмазные палочки толщиной в корпус пчелы, на одну из них он надел 64 золотых диска, и с момента сотворения мира без устали, сменяя друг друга, жрецы переносят диски с одной палочки на другую в соответствии с описанными правилами. Когда жрецы перенесут все диски с первой палочки на третью,— гласит легенда.— наступит конец света.
Давайте разберемся, как же перенести диски с первого стержня на третий, а за одно выясним, скоро ли наступит обещанный конец света.
Если бы в пирамиде был только один диск, то решение очевидно — перенесем его на третий стержень, и дело с концом. Мы выполнили требуемое задание за один ход. А если бы было два диска? Тогда положим сначала меньший диск на второй стержень, затем положим второй диск на третий стержень, затем пренесем и меньший диск на третий стержень, положив его поверх второго. Все. За три действия мы смогли переложить оба диска на третий стержень. Отметим, что 1=2^1 — 1, а 3=2^2 — 1. Теперь предположим, что мы умеем перекладывать на третий стержень пирамиду из n дисков за 2^n—1 действие. Покажем, что в таком случае можно перенести на третий стержень и пирамиду из n + 1 дисков, притом за 2^(n+1) — 1 действие.
Действительно, пусть на пирамиде лежит n+1 дисков. На вромя изменим нумерацию стержней: второй назовем третьим, а третий — вторым. Теперь мы можем перенести n верхних дисков с первого стержня на третий, произведя 2^n — 1 действие. На первом стержне остался лишь один диск. Перенесем его на свободный второй стержень. Снова перенумеруем стержни: вернем второму стержню номер три, первому дадим номер два, а третьему — номер один. Теперь у нас на первом стержне лежит n дисков, второй — свободен, а на третьем лежит самый большой диск. Осталось перенести с первого стержня на третий n дисков, что мы умеем делать за 2^n — 1 операцию. Все. Мы собрали на третьем стержне все n+1 дисков, совершив 2^(n+1) — 1 действие.
Отсюда, в соответствии с принципом математической индукции, вытекает, что для любого натурального числа к можно, имея пирамиду с k дисками, перенести их с первого стержня на третий, соблюдая правила, за 2^k — 1 действие.
Приведенное доказательство нетрудно оформить в виде алгоритма действий. Именно такой алгоритм и предлагается программистам в упомянутых книгах для его записи на том или ином алгоритмическом языке.
Нетрудно показать, что меньше чем за 2^k — 1 действие перенести k дисков с первого стержня на третий невозможно. Поэтому легендарным жрецам понадобится 2^64—1 действие, чтобы исполнить свою работу. Если тратить на каждое действие лишь по одной секунде, то понадобится 18 446 744 073 709 551 615 с, т. е. более 500 миллиардов лет.
Присмотримся повнимательнее к процессу переноса дисков. Для этого перенумеруем их в порядке возрастания: первый — самый маленький и т. д. Теперь начнем переносить диски в соответствии с алгоритмом и будем записывать номера переносимых дисков:
1213121412131215121312141…
Любопытно, что каждый нечетный перенос — это перенос первого диска. Еще одно наблюдение: расположим стержни в вершинах равностороннего треугольника и понаблюдаем за движением первого диска. Оказывается, что он движется по кругу в одну и ту же сторону; при этом, если начальное количество дисков четно, то по часовой стрелке, а если нечетно — против. Эти наблюдения позволили в 1961 году сформулировать следующий алгоритм переноса дисков:
сначала переносим первый диск, потом не первый, затем снова первый, потом не первый и т. д., причем первый диск переносится в одном направлении: по часовой стрелке в случае четного количества дисков и против часовой стрелки, в случае их нечетного количества.
Заметим, что указание «переносится не первый диск» полностью определяет, какой диск и куда следует переносить в данный момент, поскольку меньший диск всегда кладется на больший.
Недавно школьник из г. Перми Миша Федоров предложил еще один алгоритм, осуществляющий, как и только что описанный, перенос k дисков с первого стержня на третий за 2^k — 1 действие.
Миша вводит понятие «пустой башни». Стержни с нанизанными на них дисками он называет башнями, а башню, которая не участвует в операции переноса диска в этот момент, называет пустой. Алгоритм М. Федорова формулируется очень коротко:
в процессе перекладывания пустая башня должна двигаться по кругу в одном и том же направлении: по часовой стрелке, если число дисков нечетно, и против часовой стрелки, если их число четно.
Свою работу Миша Федоров с успехом доложил на Всесоюзной научно-технической конференции школьников. Заметим, что если первый алгоритм приводит к необходимому результату по построению, то справедливость второго и третьего следует доказывать, и это не очень просто. Хотя на самом деле все три алгоритма являются просто различными записями одного и того же процесса переноса дисков.
Существенно другой процесс возникает в том случае, если еще усложнить правила переноса. Наш читатель А. Тарасенко предлагает найти алгоритм, позволяющий переносить диски с первого стержня на третий, в котором первый диск ни разу не оказывался бы на втором стержне. Он утверждает, что такая процедура возможна за 2* 3^(k-1) — 1 действие. И вообще, если запретить второму диску оказываться на втором стержне, то количество перекладываний становится равным 2^2 * 3^(k-2) —1. И вообще, если запретить класть на второй стержень n-й диск, то понадобится 2^n * 3^(k-n) —1 действие.
Еще об одной модификации этой головоломки мы писали в предыдущем номере журнала (на 4 странице обложки). В. Панаев предлагает рассмотреть вопрос: всегда ли возможно перенести диски с первого стержня на третий, если первоначально они лежали на первом стержне в произвольном порядке. Приводим доказательство того, что такое перекладывание всегда возможно.
Чтобы доказать возможность такого перекладывания, сначала разберемся с более простой задачей. Пусть требуется собрать пирамиду из дисков, нанизанных на два стержня, при свободном третьем, причем диски расположены на стержнях по возрастанию диаметров. Кроме того, предположим, что такую задачу мы уже умеем решать для любого меньшего количества дисков.
Пусть самый крупный диск находится на первом стержне, тогда чтобы собрать пирамиду на третьем стержне, необходимо сделать три операции:
- собрать на втором стержне пирамиду без самого большого диска;
- переместить самый большой диск на третий стержень;
- переместить пирамиду со второго стержня на третий.
Все три операции мы можем сделать. Действительно, первую операцию мы можем сделать по предположению, вторая операция очевидна, а третья — обычное перемещение в головоломке «Ханойская башня», которое мы уже научились совершать.
Теперь вернемся к основной задаче. На первом стержне находятся диски в произвольном порядке, второй и третий стержни свободны. Постараемся разложить диски на втором и третьем стержнях в порядке возрастания. Начнем такое перекладывание и продолжим его, пока это возможно. При этом мы переложим не менее двух дисков. Если нам повезет, то мы сразу переложим все диски и перейдем к уже решенной задаче. А если не повезет? Пусть некоторый диск уже нельзя положить ни на второй, ни на третий стержень. Мысленно отделим на этих стержнях диски, меньшие рассмотренного диска. Соединим эти части вместе на втором стержне. Это мы уже научились делать. Теперь перенесем злосчастный диск на третий стержень и тем самым мы устраним возникшую трудность. Можем продолжать перекладывание. В результате все диски окажутся собранными на втором и третьем стержнях, а теперь собирать из них башню мы уже умеем. Итак, доказательство закончено.
Можно рассмотреть и такую задачу: все диски разложены в произвольном порядке на всех трех стержнях, требуется собрать их на одном. Эта задача также всегда разрешима.
В. Пинаев предлагает назвать свою головоломку П-башней, что же, можно согласиться с таким названием. Заметим, что идея этой головоломки идет от кубика Рубнка: запутаем расположение частей головоломки, а потом постараемся привести ее к первоначальному виду с помощью разрешенных действии.
В литературе рассматриваются «Ханойские башни» и с большим количеством стержней, например, в недавно вышедшей книге Ж. Арсака «Программирование игр и головоломок» (М.: Наука, 1990).
Статья взята из журнала «Квант».
