«Икосаэдрическая игра» и «Ханойская башня». Ч. 2

Что же общего у «Ханойской башни» с игрой, придуманной Гамильтоном? Чтобы понять, как эти две знаменитые головоломки связаны между собой, рассмотрим сначала пирамиду из трех колец, на которых по порядку сверху вниз нанесены буквы А, В и C. Следуя описанному выше алгоритму решения задачи, кольца нужно перемещать в следующей последовательности: ABAC ABA.

Обозначим теперь через А, В и С три оси координат, выбранные в направлениях, параллельных осям правильного шестигранника — куба (на рис. 3 — слева).

Рис. 3 - Путь Гамильтона, проходящий по ребрам куба (слева). Оси координат выбраны параллельно ребрам куба и обозначены буквами А, В и С. Путь последовательно идет по направлениям осей ABAC ABA. Справа показан путь Гамильтона, проходящий по ребрам четырехмерного куба, спроектированного в трехмерное пространство. Оси четырех координат гиперкуба обозначены буквами А, В, С и D. Путь последовательно идет по направлениям осей ABACABADABACABA. В том же порядке нужно перекладывать четыре диска в «Ханойской башне»

Если, обходя ребра куба, мы будем двигаться по направлениям этих осей в последовательности ABAC ABA, то наш маршрут окажется одним из гамильтоновых путей! Кроув заметил, что этот результат допускает обобщение: порядок перекладывания дисков при игре в «Ханойскую башню» в точности совпадает с порядком, в котором мы проходили направления координатных осей при следовании по гамильтонову пути на n-мерном кубе.

Поясним сказанное на еще одном примере. Хотя мы и не можем изготовить модель четырехмерного куба (называемого также гиперкубом или тессерактом), тем не менее ребра четырехмерного куба можно спроецировать на трехмерную модель, изображенную на рис. 3. Сеть ребер этой модели топологически эквивалентна сети ребер гиперкуба. Обозначим оси координат буквами А, В, С и D. Координата D означает расстояние, проходимое по ребрам гиперкуба. Тогда порядок перекладывания для пирамиды из четырех колец будет таким ABACABADABACABA. Следуя по ребрам гиперкуба в направлениях, указанных этой последовательностью, мы пройдем гамильтонов путь. Аналогичные рассуждения показывают, что перекладывание пяти колец соответствует пути Гамильтона, проложенному по ребрам пятимерного гиперкуба, перекладывание шести колец — гамильтонову пути, проходящему по ребрам шестимерного гиперкуба, и т. д.

Доказательство того, что п колец можно перенеси с одного колышка на другой в (2ⁿ — 1) приемов, довольно простое и может послужить хорошим упражнением на применение метода полной математической индукции.

Сходство, или, если воспользоваться научным термином, изоморфизм, решений задач о Ханойской башне и пути Гамильтона на кубе и гиперкубе перестает быть столь удивительным, когда обнаруживается, что и в том и в другом случаях последовательности ходов представляют собой набор чисел, хорошо знакомый каждому, кому доводилось работать на компьютере с двоичным представлением чисел.

Выпишем числа от 1 до 8 и обозначим столбцы буквами А, В, С и D так, как показано на рис. 4.

Рис. 4 - Таблица двоичных чисел

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

Таблица эта часто используется в математических головоломках. Но самый известный пример — это двоичное разбиение дюймового обрезка обычной линейки (рис. 5).

Рис. 5 - Двоичные деления дюйма

Нетрудно понять, откуда возникает последовательность — она образуется при делении дюймового отрезка на две, четыре, восемь и шестнадцать частей.

В данном материале использована книга "Математические головоломки и развлечения" (автор - Гарднер Мартин).