Текст книги "Математические головоломки и развлечения"

Автор книги: Мартин Гарднер

сообщить о нарушении

Текущая страница: 4 (всего у книги 30 страниц)

Согласившись с предложенной выше программой обследования нечерных предметов, не являющихся в то же время воронами, или цвета волос машинисток, мы столкнемся с небольшим затруднением: малым числом обследуемых объектов. Если же мы попытаемся установить, все ли вороны черные, то обнаружится огромная диспропорция между числом всех ворон на земле и числом нечерных предметов. Каждый согласится, что проверка всех нечерных предметов представляет собой весьма неэффективный способ исследования. Наш вопрос несколько тоньше: есть ли рациональное зерно в утверждении о том, что обнаружение красной коровы в том или ином смысле может служить примером, подтверждающим выдвинутую гипотезу? Становится ли наша первоначальная гипотеза хоть немного более правдоподобной при обнаружении подтверждающего примера, по крайней мере если речь идет о конечных множествах (рассмотрение бесконечных множеств завело бы нас слишком далеко)? Одни логики считают, что подтверждающий пример увеличивает правдоподобие гипотезы, другие в этом сомневаются. Они замечают, например, что красную корову точно с таким же основанием можно считать подтверждающим примером гипотезы «все вороны белые». Каким образом обнаружение отдельного объекта может изменить правдоподобие одной из двух взаимоисключающих гипотез?

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

Глава 6. «ИКОСАЭДРИЧЕСКАЯ ИГРА» И «ХАНОЙСКАЯ БАШНЯ»

Вряд ли что-нибудь может произвести большее впечатление на математика, чем открытие связи между двумя на первый взгляд никак не связанными между собой математическими структурами.

Именно такое открытие сделал Д. У. Кроув. Он обнаружил связь между двумя популярными головоломками прошлого века – «Икосаэдрической игрой» и «Ханойской башней». Сначала мы расскажем о каждой головоломке в отдельности, а затем покажем ту неожиданную связь, которая существует между ними.

Игру с икосаэдром придумал в пятидесятых годах прошлого века знаменитый ирландский математик Уильям Р. Гамильтон. На примере этой игры он хотел продемонстрировать некоторые не совсем обычные свойства разработанного им исчисления, во многом схожего с принадлежащей тому же автору теорией кватернионов (предшественницей современного векторного анализа). Исчисление позволяло решать ряд сложных задач об обходе ребер пяти новых, тел, и в частности икосаэдра и додекаэдра. Гамильтон назвал свое исчисление икосаэдрическим, хотя в действительности в придуманной им игре приходится совершать обход ребер додекаэдра.

В 1859 году Гамильтон продал игру за 25 долларов одному лондонскому дельцу. Позднее она в различных видах появлялась в Англии и других европейских странах. Биограф Гамильтона сообщает, что эти 25 долларов были единственными деньгами, которые получил известный математик за свои открытия и научные труды.

Гамильтон придумал много игр и головоломок, связанных с додекаэдром, но самой интересной из них была следующая. Начав с любой вершины додекаэдра (каждой его вершине Гамильтон дал название какого-нибудь крупного города), нужно было совершить «кругосветное путешествие» – обойти ровно один раз все ребра правильного многогранника и вернуться в исходную вершину.

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

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

Рис. 23 Додекаэдр (слева), проколотый (место прокола указано точкой) и растянутый на плоскости (справа). Размеры отдельных звеньев сети прямых на плоскости не совпадают с длиной ребер додекаэдра, но топологически сеть прямых на плоскости и сеть, образованная ребрами додекаэдра, эквивалентны.

Топологически эта сеть эквивалентна сети, образуемой ребрами «настоящего», несплющенного додекаэдра, но, разумеется, с плоской сетью обращаться намного удобнее, чем с объемной. Совершая «кругосветное путешествие» по этой сети («карте додекаэдра»), удобно отмечать каждую вершину, в которой вы побывали, фишкой.

Если все вершины додекаэдра эквивалентны, то существуют только два различных гамильтоновых пути, и любой из них является зеркальным отражением другого. Если же мы введем для каждой вершины особое обозначение и будем считать различными пути, проходящие через все 20 вершин в различном порядке, то таких путей окажется 30 (путь, проходимый в обратном направлении, мы не отличаем от пути, проходимого в прямом направлении). Гамильтоновы пути точно так же можно построить на четырех других Платоновых телах и на многих, хотя и не на всех, полуправильных многогранниках.

Известную игру «Ханойская башня» придумал французский математик Эдуард Люка. В 1883 году ее продавали как забавную игрушку. Первоначально она называлась «Профессор Клаус (Claus) из Коллеж Ли-Су-Стьян (Li-Sou-Stian)» но вскоре обнаружилось, что таинственный профессор из несуществующего коллежа – не более чем анаграмма фамилии изобретателя игры – профессора Люка (Lucas) из коллежа Сен-Луи (Saint Louis). Вид игрушки показан на рис. 24.

Рис. 24 «Ханойская башня»

Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причем нельзя класть большее кольцо на меньшее.

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

Таким образом, три диска можно перенести с помощью семи перекладываний; для четырех дисков понадобится пятнадцать перекладываний, для пяти – 31 и т. д. Для восьми колец, изображенных на рис. 24, потребуется 255 перекладываний. В первоначальном описании игрушка называется упрощенным вариантом мифической «Пирамиды браминов» в храме индийского города Бенареса. Как гласит предание, эта пирамида состоит из 64 золотых колец, которые и по сей день перекладывают жрецы храма. Как только им удастся справиться со своей задачей, храм рассыплется в пыль, грянет гром и мир исчезнет. О конце мира еще, пожалуй, можно спорить, но то, что храм за это время обратится в пыль, несомненно. Формула 2⁶⁴ – 1 дает двадцатизначное число 18446744073 703551615.

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

(Получившееся число не является простым, но если число колец увеличить до 89, 107 или 127, то в каждом случае нужное число перемещений будет простым. Эти числа называются числами Мерсенна: простые числа, которые можно представить в виде 2ⁿ – 1.

Сам Люка был первым, кто установил, что число 2¹²⁷ – 1 простое.

Это огромное 39-значное число было самым большим из всех известных вплоть до 1952 года простых чисел. В 1952 году с помощью большой электронно-вычислительной машины было найдено пять новых чисел Мерсенна. Самое большое из них имеет вид 2²²⁸¹ – 1.

Существует много аргументов в пользу того, что число 2⁸¹⁹¹ – 1 также простое, но пока это не доказано.)

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

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

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

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

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

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

* * *

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


[Закрыть] Задача легко обобщается на любое число колышков.

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

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

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

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

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

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

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

Глава 7. ЗАНИМАТЕЛЬНЫЕ ТОПОЛОГИЧЕСКИЕ МОДЕЛИ

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

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

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

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

На первый взгляд кажется, что в результате мы получаем два вложенных друг в друга листа Мёбиуса. В самом деле, просунув палец между полосками бумаги и обводя им вокруг них до тех пор, пока не возвратитесь в исходную точку, вы «докажете», что фигура состоит из двух отдельных лент. Насекомое, заползшее в щель между бумажными лентами, могло бы совершать такое «кругосветное путешествие» до бесконечности. При этом оно всегда ползало бы по одной полоске бумаги, спинка его касалась бы другой полоски, и ему нигде не удалось бы найти точку, в которой «пол» сходится с «потолком». Отсюда наделенное разумом насекомое заключило бы, что оно путешествует между поверхностями двух отдельных полосок.

Но представим себе, что наше насекомое оставило на полу метку и совершает обход вокруг полосок до тех пор, пока не встретит ее снова. Тогда оно обнаружит, что метка находится не на полу, а на потолке и что необходимо обойти еще раз вокруг полосок, чтобы метка снова очутилась на полу! Насекомое вряд ли должно обладать недюжинным воображением, чтобы понять, что и пол и потолок образуют одну сторону одной-единственной полоски. [Еще забавнее допустить, что разумное насекомое строит по обеим сторонам ленты-улицы шарообразные дома и, как полагается, вешает на них номера-указатели – по правой стороне четные, а по левой нечетные. Казалось бы, задача простая. Но, начав свою операцию с некоторого места – площади, где поставлен двумерный памятник Мёбиусу, – оно будет весьма обескуражено, когда, обойдя всю «улицу», вернется на площадь с другой стороны! С небывалой трудностью встретится в таком двумерном городе ГАИ: как установить в нем правостороннее движение?] То, что на первый взгляд казалось двумя вложенными друг в друга лентами, на самом деле представляет собой одну большую ленту. Но коль скоро вы развернули модель, превратив ее в одну большую ленту, перед вами встает хитроумная задача: как вернуть ленте ее первоначальный вид?

Когда наша модель имеет вид двойной ленты, два ее края идут параллельно друг другу и описывают два полных оборота. Представим себе, что эти края склеены, а сама лента сделана из тонкой резины. Тогда мы получим трубку, которую можно раздуть и превратить в тор (так топологи называют обычный бублик). Склеенные края образуют на поверхности тора замкнутую кривую: намотанную на тор спираль, состоящую из двух витков. Это означает, что, разрезав тор вдоль такой кривой, мы получим двойной лист Мёбиуса – это не что иное, как обыкновенная лента, концы которой перед тем, как их склеить, перекрутили четыре раза (каждый поворот – на 180°). Тор можно превратить в ленту, концы которой повернуты относительно друг друга на любое четное число полуоборотов, но его нельзя разрезать так, чтобы он превратился в ленту, которую перекрутили нечетное число раз. Это связано с тем, что тор – поверхность двусторонняя. Из лент двусторонними являются лишь те, которые перекручены четное число раз (напомним, что, перекручивая ленту, мы каждый раз поворачиваем ее концы на 180° относительно друг друга). Двусторонние поверхности можно получить, разрезая односторонние, хотя обратное невозможно. Если же мы хотим получить односторонние ленты (ленты с нечетным числом перекручиваний на пол-оборота каждое), разрезая поверхность без края, то нам следует обратиться к разрезанию бутылки Клейна.

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

Обычный лист Мёбиуса получают, склеивая концы перекрученной на пол-оборота ленты. Можно ли растянуть лист Мёбиуса так, чтобы его край принял форму треугольника? Оказывается, можно.

Первым, кто придумал такую модель, был Брайан Таккерман, один из четырех основоположников искусства складывать флексагоны (см. главу 1). На рис. 29 показано, как следует разрезать, сложить и склеить лист бумаги, чтобы построить модель Таккермана.

Рис. 29 Лист Мёбиуса с треугольным краем, придуманный Брайаном Таккерманом. Перечертив изображенную на этом рисунке выкройку в увеличенном масштабе, можно склеить модель, показанную вверху.

Для изготовления модели необходимо проделать следующие операции: 1) вырезать выкройку фигуры из бумаги; 2) перегнуть ее вдоль сплошных линий так, чтобы ребро сгиба было обращено острием вверх; 3) перегнуть выкройку вдоль пунктирных линий так, чтобы острие сгиба было обращено вниз; 4) намазав клеем четыре клапана, склеить выкройку так, чтобы отрезки, обозначенные одинаковыми буквами, совпали. Сплошные линии на поверхности получившегося многогранника образуют треугольный край листа Мёбиуса.

Поверхности могут быть не только односторонними и двусторонними. С точки зрения топологии, они могут отличаться друг от друга числом своих краев и их устройством. Поскольку ни число краев, ни их структуру нельзя изменить, деформируя поверхность, они называются топологическими инвариантами. Рассмотрим поверхности, имеющие не более двух краев. Будем считать, что краем могут быть либо простые замкнутые кривые, либо кривые, имеющие форму обычного простого узла. При таком предположении можно указать следующие 16 типов поверхностей (сюда не входят такие поверхности без края, как сфера, тор и бутылка Клейна):

Односторонние поверхности с одним краем

1. Край имеет форму простой замкнутой кривой.

2. Край «завязан узлом».

Двусторонние поверхности с одним краем

3. Край – простая замкнутая кривая.

4. Край «завязан узлом».

Односторонние поверхности с двумя краями

5. Оба края – простые замкнутые кривые, не зацепленные друг за друга.

6. Оба края – простые замкнутые кривые, зацепленные друг за друга.

7. Оба края завязаны в узел, но не зацеплены друг за друга.

8. Оба края завязаны в узел и зацеплены друг за друга.

9. Один край простой, другой завязан узлом; между собой края не зацеплены.

10. Один край простой, другой завязан узлом; края зацеплены.

Двусторонние поверхности с двумя краями

11. Оба края – простые замкнутые кривые, не зацепленные друг за друга.

12. Оба края – простые замкнутые кривые, зацепленные друг за друга.

13. Оба края завязаны в узел, между собой не зацеплены.

14. Оба края завязаны в узел и зацеплены друг за друга.

15. Один край простой, другой завязан в узел; друг за друга края не зацеплены.

16. Один край простой, другой завязан в узел; края зацеплены.

Построить бумажные модели всех этих шестнадцати типов поверхностей нетрудно. Модели поверхностей 1 – 12 изображены на рис. 30, а модели остальных четырех поверхностей – на рис. 31.

Рис. 30 Бумажные модели поверхностей 1-12.

Рис. 31 Бумажные модели поверхностей 13–16.

Если некоторые из этих моделей определенным образом разрезать, то получатся довольно неожиданные результаты. Почти все, кому случалось играть с листом Мёбиуса, знают, что, разрезав его вдоль на две половины, мы получим не два отдельных листа (как можно было бы ожидать), а один большой лист. (Этот большой лист перекручен на четыре пол-оборота, следовательно, из него можно сделать двойной лист Мёбиуса, о котором мы уже говорили.) Менее известно, что если продольный разрез совершать так, чтобы он проходил от края на расстоянии одной трети ширины листа, то, вернувшись в исходную точку, мы обнаружим, что лист Мёбиуса распался на два листа Мёбиуса: большой и сцепленный с ним лист меньших размеров.

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

Когда мы говорим, что два края «зацеплены», мы имеем в виду, что они соединены так же, как два звена в цепи. Чтобы звенья можно было разнять, одно из них необходимо распилить, а через образовавшееся отверстие протащить другое. Однако две замкнутые кривые могут быть зацеплены так, что для того, чтобы их разнять, не обязательно провести одну из них через отверстие в другой. Проще всего это сделать так, как показано на рис. 32 (верхние кривые).

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

Эти кривые можно разделить, пропустив одну из лент через себя в точке А.

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

* * *

Интересную модель двойного листа Мёбиуса можно сделать из жесткого пластика. На такой модели особенно легко описать полный оборот пальцем, просунув его между «двумя» лентами.

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

Красная прокладка в такой модели принимает форму листа Мёбиуса. Точно так же всякую неориентируемую (одностороннюю) поверхность можно накрыть так называемой «двулистной» двусторонней поверхностью. Например, бутылку Клейна можно полностью накрыть тором, половина которого должна быть вывернута наизнанку. Как и при накрывании листа Мёбиуса, кажется, что эта поверхность состоит из двух отдельных поверхностей, вложенных одна в другую. Проколов такую поверхность в любой точке, мы обнаружим, что внутренняя поверхность отделена от наружной поверхностью бутылки Клейна. Тем не менее и внутренняя и наружная поверхности являются частями одного и того же тора.[14]14
  Гильберт Д., Кон-Фоссен С. Наглядная геометрия: 2-е изд.. – М.: Гостехтеоретиздат, 1951, стр. 318.


[Закрыть]