Математические головоломки и развлечения
Шрифт:
В 1859 году Гамильтон продал игру за 25 долларов одному лондонскому дельцу. Позднее она в различных видах появлялась в Англии и других европейских странах. Биограф Гамильтона сообщает, что эти 25 долларов были единственными деньгами, которые получил известный математик за свои открытия и научные труды.
Гамильтон придумал много игр и головоломок, связанных с додекаэдром, но самой интересной из них была следующая. Начав с любой вершины додекаэдра (каждой его вершине Гамильтон дал название какого-нибудь крупного города), нужно было совершить «кругосветное путешествие» — обойти ровно один раз все ребра правильного многогранника и вернуться в исходную вершину.
Иначе говоря, путь должен иметь вид замкнутой ломаной, составленной из всех ребер додекаэдра. Каждое ребро разрешается проходить только один раз. Начало
Представьте себе, что поверхность додекаэдра сделана из резины. Проткнув одну из его граней, растянем додекаэдр так, чтобы он целиком распластался на плоскости. Его ребра расположатся в виде сети, показанной на рис. 23.
Рис. 23 Додекаэдр (слева), проколотый (место прокола указано точкой) и растянутый на плоскости (справа). Размеры отдельных звеньев сети прямых на плоскости не совпадают с длиной ребер додекаэдра, но топологически сеть прямых на плоскости и сеть, образованная ребрами додекаэдра, эквивалентны.
Топологически эта сеть эквивалентна сети, образуемой ребрами «настоящего», несплющенного додекаэдра, но, разумеется, с плоской сетью обращаться намного удобнее, чем с объемной. Совершая «кругосветное путешествие» по этой сети («карте додекаэдра»), удобно отмечать каждую вершину, в которой вы побывали, фишкой.
Если все вершины додекаэдра эквивалентны, то существуют только два различных гамильтоновых пути, и любой из них является зеркальным отражением другого. Если же мы введем для каждой вершины особое обозначение и будем считать различными пути, проходящие через все 20 вершин в различном порядке, то таких путей окажется 30 (путь, проходимый в обратном направлении, мы не отличаем от пути, проходимого в прямом направлении). Гамильтоновы пути точно так же можно построить на четырех других Платоновых телах и на многих, хотя и не на всех, полуправильных многогранниках.
Известную игру «Ханойская башня» придумал французский математик Эдуард Люка. В 1883 году ее продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Коллеж Ли-Су-Стьян (Li-Sou-Stian)» но вскоре обнаружилось, что таинственный профессор из несуществующего коллежа — не более чем анаграмма фамилии изобретателя игры — профессора Люка (Lucas) из коллежа Сен-Луи (Saint Louis). Вид игрушки показан на рис. 24.
Рис. 24 «Ханойская башня»
Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причем нельзя класть большее кольцо на меньшее.
Нетрудно доказать, что решение существует независимо от того, сколько колец в пирамиде, и что минимальное число необходимых перекладываний выражается формулой 2n—1 (где n — число колец).
Таким образом, три диска можно перенести с помощью семи перекладываний; для четырех дисков понадобится пятнадцать перекладываний, для пяти — 31 и т. д. Для восьми колец, изображенных на рис. 24, потребуется 255 перекладываний. В первоначальном описании игрушка называется упрощенным вариантом мифической «Пирамиды браминов» в храме индийского города Бенареса. Как гласит предание, эта пирамида состоит из 64 золотых колец, которые и по сей день перекладывают жрецы храма. Как только им удастся справиться со своей задачей, храм рассыплется в пыль, грянет гром и мир исчезнет. О конце мира еще, пожалуй, можно спорить, но то, что храм за это время обратится в пыль, несомненно. Формула 264 — 1 дает двадцатизначное число 18446744073 703551615.
Даже если бы жрецы работали не покладая рук, днем и ночью, перенося каждую секунду по одному кольцу, чтобы закончить работу, им понадобились бы многие миллионы тысячелетий.
(Получившееся число не является простым, но если число колец увеличить до 89, 107 или 127, то в каждом случае нужное число перемещений будет простым. Эти числа называются числами Мерсенна: простые числа, которые можно представить в виде 2n — 1.
Сам Люка был первым, кто установил, что число 2127 — 1 простое.
Это огромное 39-значное число было самым большим из всех известных вплоть до 1952 года простых чисел. В 1952 году с помощью большой электронно-вычислительной машины было найдено пять новых чисел Мерсенна. Самое большое из них имеет вид 22281 — 1.
Существует много аргументов в пользу того, что число 28191 — 1 также простое, но пока это не доказано.)
Головоломку «Ханойская башня» легко сделать из восьми картонных квадратиков постепенно увеличивающегося размера (с тем же успехом можно взять игральные карты от туза до восьмерки), которые нужно перекладывать между тремя отметками на листе бумаги. Если эти отметки образуют треугольник, то задача решается для любого числа колец следующим простым способом. Начнем с самого маленького квадрата и переложим его на любую отметку. В дальнейшем этот квадратик нужно перемещать в том же направлении, что и при первом перекладывании. Затем произведем единственно возможное перемещение оставшихся квадратов, после чего снова переложим самый маленький квадрат и т. д. (Интересно заметить, что, перенумеровав «кольца» по порядку, мы добьемся неожиданного эффекта: четные квадраты будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечетные— в противоположном направлении.)
Что же общего у «Ханойской башни» с игрой, придуманной Гамильтоном? Чтобы понять, как эти две знаменитые головоломки связаны между собой, рассмотрим сначала пирамиду из трех колец, на которых по порядку сверху вниз нанесены буквы А, В и C. Следуя описанному выше алгоритму решения задачи, кольца нужно перемещать в следующей последовательности: ABAC ABA.
Обозначим теперь через А, В и С три оси координат, выбранные в направлениях, параллельных осям правильного шестигранника — куба (на рис. 25 — слева).
Рис. 25 Путь Гамильтона, проходящий по ребрам куба (слева). Оси координат выбраны параллельно ребрам куба и обозначены буквами А, В и С. Путь последовательно идет по направлениям осей ABAC ABA. Справа показан путь Гамильтона, проходящий по ребрам четырехмерного куба, спроектированного в трехмерное пространство. Оси четырех координат гиперкуба обозначены буквами А, В, С и D. Путь последовательно идет по направлениям осей ABACABADABACABA. В том же порядке нужно перекладывать четыре диска в «Ханойской башне».
Если, обходя ребра куба, мы будем двигаться по направлениям этих осей в последовательности ABAC ABA, то наш маршрут окажется одним из гамильтоновых путей! Кроув заметил, что этот результат допускает обобщение: порядок перекладывания дисков при игре в «Ханойскую башню» в точности совпадает с порядком, в котором мы проходили направления координатных осей при следовании по гамильтонову пути на n-мерном кубе.
Поясним сказанное на еще одном примере. Хотя мы и не можем изготовить модель четырехмерного куба (называемого также гиперкубом или тессерактом), тем не менее ребра четырехмерного куба можно спроецировать на трехмерную модель, изображенную на рис. 25. Сеть ребер этой модели топологически эквивалентна сети ребер гиперкуба. Обозначим оси координат буквами А, В, С и D. Координата D означает расстояние, проходимое по ребрам гиперкуба. Тогда порядок перекладывания для пирамиды из четырех колец будет таким ABACABADABACABA. Следуя по ребрам гиперкуба в направлениях, указанных этой последовательностью, мы пройдем гамильтонов путь. Аналогичные рассуждения показывают, что перекладывание пяти колец соответствует пути Гамильтона, проложенному по ребрам пятимерного гиперкуба, перекладывание шести колец — гамильтонову пути, проходящему по ребрам шестимерного гиперкуба, и т. д.