■ перемещать диски можно только по одному;
■ нельзя класть диск большего диаметра на диск меньшего диаметра;
■ снятый диск нельзя отложить в сторону — его нужно сразу надеть на один из двух других стержней.
Если вас заинтересовала эта задачка, то, за неимением дисков, предлагаю решить головоломку, используя, например, 4—5 монет разного диаметра, так же выкладывая их в виде пирамиды. Интересно, сколько времени вам понадобится для решения?
На русском языке головоломка впервые была описана в книге Е. И. Игнатьева «В царстве смекалки, или Арифметика для всех»* в 1908 году. А появилась она на 25 лет раньше во Франции. К головоломке прилагалась листовка, как бы мы сказали сейчас, — инструкция.
Заголовок листовки гласит: «Настоящая аннамская головоломка, привезённая из Тонкина профессором Н. Клаусом (из Сиама), преподавателем** колледжа Ли-Су-Стиан». Далее говорится, что эта оригинальная игра была впервые обнаружена в трудах прославленного учёного-мандарина Фер-фер-там-там’а, которые в ближайшее время будут опубликованы по указанию правительства Китая. Приводится описание головоломки и указывается, что в Японии, Китае и Тонкине в ней используются фарфоровые диски. В тексте ещё раз упоминается Н. Клаус.
Во всех современных источниках пишут о том, что головоломку «Ханойская башня» придумал французский математик Эдуард Люкa (1842—1891). Но когда и как это стало известно? Ведь долго её авторство приписывалось Н. Клаусу. Удивительно, что сам Люка, описывая головоломку в ряде своих трудов в 80-х годах XIX века, не указывал себя её автором. Впервые раздел «Ханойская башня» был представлен в его книге «Занимательная математика», изданной в 1893 году, через два года после смерти учёного, во вступлении к которой он писал: «Один из моих друзей, профессор Н. Клаус…».
Почему же всё-таки Люка?
Первым, кто попытался узнать, кто «скрывается» под именем человека с «европейской» фамилией Клаус, публикующего труды китайского учёного Фер-фер-там-там’а с описанием аннамской головоломки и рассказывающего о её использовании в Японии, Китае и Тонкине, был французский журналист, историк и популяризатор науки Анри де Парвиль. В марте 1884 года он опубликовал в журнале «La Nature» в разделе «Занимательная математика» статью «Ханойская башня и Тонкинский вопрос», в которой связал создание головоломки с трудами профессора Э. Люка из лицея Сен-Луи. Парвиль написал, что если переставить буквы в имени человека, подготовившего листовку к головоломке, — «N. Claus de Siam», то можно получить имя «Lucas d’Amiens», а из названия колледжа «Li-Sou-Stain» складывается название лицея «Saint-Louis».
К этому можно добавить ещё два момента.
Во-первых, в конце инструкции, прилагаемой к головоломке, её автор (Н. Клаус) ссылается на книгу Люка «Занимательная математика», то есть, выражаясь современным языком, делает рекламу книге учёного. Во-вторых, у человека, сидящего у основания башни на картинке на лицевой стороне коробки, есть татуировка на животе: «А. U», а Люка имел звание «Аgrege de l’universite» (эту надпись можно перевести как «ассоциированный с университетом»), что давало ему право преподавать в высших учебных заведениях.
И ещё: наверное, самый весомый аргумент в пользу того, что на самом деле «Ханойскую башню» изобрёл Эдуард Люка, долгое время скрывавшийся под именем загадочного профессора Клауса, — это записка в коробке с оригинальным экземпляром головоломки, хранящимся в Музее искусств и ремёсел в Париже. Текст в ней, скорее всего, написан Эдуардом Люка: «Ханойская башня, арифметическая игра… изобретённая Эд. Люка. Предоставлена автором. 1888 г.»…
Источник иллюстраций: Hinz A. M., Klavzar S., Petr C. The Tower of Hanoi — Myth and Math. 2-nd Edition. Springer, 2018.
Выражаю благодарность Полу Стокмейеру (Paul Stockmeyer), профессору в отставке Колледжа Уильяма и Мэри Вильямсбург, штат Вирджиния, США, за предоставление информации и иллюстраций, использованных в статье.
***
Подробности для любознательных
А если дисков 64?
В своей книге «В царстве смекалки, или Арифметика для всех» российский и советский педагог-математик и автор научно-популярных книг Емельян Игнатьевич Игнатьев пишет, что если вместо 8 дисков взять 64, то получается задача, связанная с древнеиндийской легендой. Легенда эта гласит, будто в городе Бенаресе, под куполом главного храма, в том месте, где находится середина Земли, бог Брама поставил вертикально на бронзовой площадке три алмазные палочки, каждая длиною в локоть и толщиною в брюшко пчелы. При сотворении мира на одну из этих палочек были надеты 64 кружка из чистого золота с отверстиями посередине, которые образовали род усечённого конуса, так как диаметры их шли в возрастающем порядке, начиная сверху. Жрецы, сменяемые один другим, днём и ночью без устали трудятся над перенесением этой колонны кружков с первой палочки на третью, пользуясь второй как вспомогательной, причём они обязаны соблюдать указанные условия. Когда, соблюдая все эти условия, жрецы перенесут все 64 кружка с первой палочки на третью, наступит конец мира.
Когда же, согласно легенде, ждать этот роковой день?
Узнать можно, только решив головоломку. Порассуждаем. Если диск один, задача решается легко. Предположим, что в головоломке только два диска. В этом случае надо сначала переложить меньший диск на какой-то другой стержень, затем большой — на свободный стержень и, наконец, меньший диск — на большой диск (всего три перекладывания).
Чтобы решить головоломку при наличии трёх дисков, надо:
■ переместить два верхних диска на один из стержней (понадобится три перекладывания);
■ переместить самый большой диск на свободный стержень;
■ переместить на этот же стержень первые два диска (также три перекладывания).
Общее число перекладываний — 7.
Рассуждая таким образом, можно установить, что при четырёх дисках число перекладываний составит 7 + 1 + 7 = 15, при пяти — 15 + 1 + 15 = 31 и т. д.
В общем случае при наличии n дисков задача решается за 2n — 1 перемещений. Расчёты показывают, что при n = 64 количество перемещений равно 18 446 744 073 709 551 615. Если допустить, что один диск переносится всего за одну (!) секунду, то на перемещение пирамиды из 64 дисков понадобится 18 446 744 073 709 551 615 секунд или примерно 584,9 миллиарда лет. Так что беспокоиться о приближении «конца мира» преждевременно.
