Мартин Гарднер - Математические головоломки и развлечения

Головоломку «Ханойская башня» легко сделать из восьми картонных квадратиков постепенно увеличивающегося размера (с тем же успехом можно взять игральные карты от туза до восьмерки), которые нужно перекладывать между тремя отметками на листе бумаги. Если эти отметки образуют треугольник, то задача решается для любого числа колец следующим простым способом. Начнем с самого маленького квадрата и переложим его на любую отметку. В дальнейшем этот квадратик нужно перемещать в том же направлении, что и при первом перекладывании. Затем произведем единственно возможное перемещение оставшихся квадратов, после чего снова переложим самый маленький квадрат и т. д. (Интересно заметить, что, перенумеровав «кольца» по порядку, мы добьемся неожиданного эффекта: четные квадраты будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечетные— в противоположном направлении.)

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

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

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

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

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

* * *

Доказательство того, что п колец можно перенеси с одного колышка на другой в (2 n— 1) приемов, довольно простое и может послужить хорошим упражнением на применение метода полной математической индукции. [13] Mathematics Teacher: 44.-1951, p. 505; 45.-1952, p. 522. Задача легко обобщается на любое число колышков.

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

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

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

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

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

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

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

Многим читателям этой книги известно, что лист Мёбиуса представляет собой геометрический курьез: поверхность, имеющую лишь одну сторону и один край. Изучением таких фигур занимается раздел математики, который носит название топологии. У людей, интересующихся математикой не всерьез, а от случая к случаю, может сложиться впечатление, что тополог — это праздный любитель забав, проводящий все свое время за конструированием листов Мёбиуса и других занимательных математических моделей. Если бы такие люди раскрыли любой современный учебник топологии, то они были бы весьма поражены, увидев страницы, сплошь испещренные математическими символами, среди которых изредка встречаются картинки или чертежи. Топология и в самом деле возникла из рассмотрения геометрических головоломок, но сейчас она давно уже разрослась в непроходимые дебри абстрактной теории. В наши дни топологи с подозрением относятся к теоремам, при доказательстве которых приходится использовать наглядные представления.

Тем не менее серьезные топологические исследования служат неисчерпаемым источником занимательных моделей самого необычайного свойства. Рассмотрим, например, двойной лист Мёбиуса.

Он получится, если наложить друг на друга две полоски бумаги, перекрутить их, повернув как единое целое на пол-оборота, и соединить концы так, как показано на рис. 28.

Рис. 28 Двойной лист Мёбиуса можно сделать из двух полосок бумаги (слева), перекрутив их на полоборота и склеив так, как показано на рисунке справа.