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

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

Глава 12. ПОЛИМИНО

Термин «полимино» ввел в употребление известный математик Соломон В. Голомб. В своей статье «Шахматные доски и полимино»,[23]23
  American Mathematical Monthly. – 61, 1954, pp. 675–682.


[Закрыть] написанной им еще в бытность его аспирантом Гарварда, Голомб определил полимино как «односвязную» фигуру, составленную из квадратов. Односвязность фигуры означает, что каждый входящий в нее квадрат имеет по крайней мере одну сторону, общую с другим входящим в нее же квадратом. Шахматист, добавляет Голомб, сказал бы, что квадраты составлены «ходом ладьи», потому что ладья могла бы обойти все квадраты полимино за конечное число ходов.

На рис. 64 показаны мономино и все возможные фигуры полимино из двух, трех и четырех квадратов.

Рис. 64

Существует только один тип домино, два типа тримино и пять типов тетрамино. У пентамино число различных фигур возрастает сразу до двенадцати. Все они показаны на рис. 65.

Рис. 65

Асимметричные фигуры, переходящие друг в друга при переворачивании, считаются одной и той же фигурой. Во всех развлечениях с полимино, о которых пойдет речь в этой главе, наряду с любой асимметричной фигурой можно использовать и ее зеркальное отражение.

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

Существует 35 различных разновидностей гексамино и 108 разновидностей гептамино. В число последних включено и одно спорное гептамино, изображенное на рис. 66.

Рис. 66

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

В главе 3 задача о полимино (задача 3) рассматривалась в связи с расположением домино на шахматной доске с вырезанными углами. В статье Голомба обсуждается много не менее интересных аналогичных задач о полимино высших порядков. Очевидно, что покрыть шахматную доску размером 8x8 клеток одними лишь тримино невозможно (хотя бы потому, что число 64 не делится на 3). Можно ли покрыть ту же доску двадцать одним прямым тримино и одним мономино? С помощью хитроумной раскраски квадратов, из которых состоят кости тримино, в три различных цвета Голомб показал, что это возможно лишь тогда, когда мономино закрывает один из заштрихованных квадратов на рис. 67.

Рис. 67

С другой стороны, методом полной математической индукции можно доказать, что двадцать одним тримино и одним мономино можно полностью покрыть шахматную доску независимо от того, где находится мономино. Оказывается, доску можно покрыть и шестнадцатью одинаковыми тетрамино любого типа, кроме зигзагообразного. Зигзагообразные тетрамино нельзя уложить даже так, чтобы закрыть хотя бы полоску у края доски. Если доску раскрасить разноцветными полосками, то можно доказать, что 15 L-образных тетрамино и одно квадратное тетрамино не могут образовывать покрытия. Раскрасив доску полосами в виде зигзагов, мы докажем, что квадратное тетрамино плюс любая комбинация прямых и зигзагообразных тетрамино также не могут покрывать целиком всю доску.

При взгляде на пентамино, изображенные на рис. 65, невольно возникает вопрос: можно ли из этих 12 фигур и одного квадратного тетрамино сложить обычную шахматную доску размером 8x8 клеток?

Впервые решение этой задачи появилось в 1907 году. Оно принадлежало Генри Дьюдени.[24]24
  Dudeney H. The Canterbury Puzzles. – London: 1907. Имеется русское издание: Дьюдени Г. Кентерберийские головоломки. – М.: Мир, 1979.


[Закрыть] В решении Дьюдени квадратное тетрамино примыкает к боковой стороне доски.

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

Самые интересные результаты были опубликованы в декабрьском номере того же журнала за 1954 год. Многое из того, о чем здесь будет рассказано, взято из этого номера и из неопубликованной статьи Голомба, посвященной аналогичным теоремам, которые он доказал независимо от других.

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

Рис. 68 Доказательство Т. Р. Доусона.

Квадратное тетрамино в комбинации с L-образным пентамино образует квадрат 3x3. При вращении большого квадрата квадратичное пентамино на каждом рисунке оказывается в четырех различных положениях.

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

Никто не знает, сколько всего существует решений этой задачи, но похоже, что их больше 10 000. В 1958 году Дана С. Скотт (аспирантка-математик из Принстона) с помощью компьютера нашла все возможные решения с квадратом в центре доски. За три с половиной часа компьютер вьщал полный список из 65 различных решений (решения, получаемые одно из другого при поворотах и отражениях доски, не считаются различными и входят в этот список как одно решение).

При составлении программы было удобно разбить все решения на три класса в зависимости от расположения креста относительно центрального квадрата. На рис. 69 показаны решения всех трех классов. Компьютер нашел 20 решений первого, 19 второго и 26 третьего классов.

Исследуя все 65 решений, мы обнаруживаем несколько интересных фактов. Не существует решения, в котором прямое тетрамино не прилегало бы по всей своей длине к стороне доски. Для решений, в которых квадрат расположен не в центре, это утверждение неверно. В семи решениях (принадлежащих к первому и третьему классам) нет «перекрестков», то есть точек, где бы соприкасались углы четырех фигур. Отдельные знатоки считают, что «перекрестки» портят красоту рисунка. У третьего решения (рис. 69) есть интересное свойство: фигуру можно перегнуть пополам вдоль прямой линии. Существует 12 таких решений, все они относятся к третьему классу, и у каждого есть «перекрестки».

Рис. 69

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

Такая «неполная» доска выглядит довольно изящно (три варианта сборки показаны на рис. 70).

Рис. 70

Из двенадцати пентамино можно сложить прямоугольники 6 х 10; 5 х 12; 4 х 15 и 3 х 20 (рис. 71).

Рис. 71 Прямоугольники, составленные из пентамино.

Прямоугольник 3 х 20, со всех точек зрения более сложный, мы предлагаем интересующемуся читателю собрать самостоятельно. Существует только два различных решения этой задачи, если не считать вращений и отражений. Обратите внимание, что на рис. 71 прямоугольник 5 х 12 собран из двух прямоугольников 5 х 7 и 5 х 5. Два прямоугольника 5x6, изображенные на рис. 72, можно сложить так, что получится прямоугольник либо 5 х 12, либо 6 х 10.

Рис. 72

Профессор Р. Робинсон и Дж. Таккер независимо друг от друга придумали задачу, которая получила название задачи об утроении.

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

Задача об утроении допускает много изящных решений, три из них показаны на рис. 73.

Рис. 73 Схемы утроения.

Задача об утроении решается для любого из двенадцати пентамино.

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

Типичное решение такой задачи показано на рис. 74.

Рис. 74 Схема «двойного удвоения».

Другая задача состоит в том, чтобы из всех 12 фигур пентамино сложить прямоугольник 5 х 13, имеющий в центре отверстие в форме одной из этих фигур. Задача решается всегда независимо от того, с какой из 12 фигур пентамино совпадает форма отверстия. Одно из решений приведено на рис. 75.

Рис. 75

На рис. 76 показана еще одна интересная задача. Из двенадцати пентамино требуется сложить развертку куба с ребром, равным

Куб получается, если рисунок согнуть по пунктирным линиям.

Рис. 76 Развертка куба, сложенная из пентамино.

Какое минимальное число пентамино надо положить на шахматную доску, чтобы ни для одного из оставшихся пентамино места больше не было? Этот любопытный вопрос придумал Голомб; сам он считает, что это число равно пяти.

На рис. 77 изображена одна из таких конфигураций.

Рис. 77 Игра на шахматной доске фигурами пентамино.

Эта задача натолкнула Голомба на мысль играть на шахматной доске картонными пентамино, вырезанными точно по размерам квадратов доски. (Мы рекомендуем читателю изготовить такой набор пентамино, ибо он годен не только для игры, но и для того, чтобы решать и придумывать задачи.)

Двое или более игроков по очереди выбирают любое но и закрывают им любые клетки доски. У фигур нет «верхней» и «нижней» стороны. Как и во всех других задачах этой главы, пентамино могут быть асимметричными. Проигрывает тот, кто не сможет поставить свое пентамино.

Голомб пишет:

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

1. Старайтесь играть так, чтобы всегда оставалось место для четного числа «костей» (если вы играете вдвоем).

2. Если вы затрудняетесь проанализировать создавшуюся позицию, постарайтесь по возможности усложнить ее, чтобы противник оказался в еще более затруднительном положении, чем вы».

Поскольку 35 костей гексамино покрывают площадь в 210 квадратиков, невольно возникает мысль: а нельзя ли сложить из них прямоугольники размером 3 х 70, 5 х 42, 6 х 35, 7 х 30, 10 х 21 или 14 х 15? Я всерьез подумывал о том, чтобы назначить премию в 1000 долларов тому из читателей, кто сумеет построить один из этих шести прямоугольников, но мысль о тех долгих часах, которые ему придется затратить понапрасну, чтобы отыскать решение, вынудила меня отказаться от моего намерения. Дело в том, что все подобные попытки, как доказал Голомб, заранее обречены на провал. Его доказательство может служить прекрасным примером использования методов комбинаторной геометрии – мало известной отрасли математики, выводы которой широко используются в технике при отыскании оптимальных способов подгонки стандартных деталей. Для нас особый интерес представляют два примера:

а) раскраска частей интересующей нас фигуры в различные цвета для большей наглядности;

б) принцип «проверки на четность», основанный на использовании комбинаторных свойств четных и нечетных чисел.

Прежде всего раскрасим наши прямоугольники подобно шахматной доске в черные и белые квадраты. И тех и других должно быть нечетное число: 105 черных квадратов и 105 белых.

Перебрав 35 фигур гексамино, мы обнаружим, что 24 из них всегда покрывают три черных и три белых квадрата, то есть нечетное число квадратов каждого цвета. Число таких «нечетных гексамино» четно, а поскольку произведение четного числа на нечетное четно, мы можем утверждать, что все вместе 24 «четных» гексамино покроют четное число квадратов каждого цвета.

Остающиеся 11 гексамино имеют такую форму, что каждым из них можно накрыть четыре квадрата одного цвета и два другого, то есть четное число квадратов того и другого цвета. Число таких «четных гексамино» нечетно, но опять же. поскольку произведение четного числа на нечетное есть число четное, мы можем с уверенностью утверждать, что эти 11 фигур накрывают четное число квадратов каждого цвета. (На рис. 78 и 79 разбиты на группы 35 гексамино четных и нечетных фигур.)

Рис. 78 Двадцать четыре «нечетных» гексамино.

Рис. 79 Одиннадцать «четных» гексамино.

Наконец, поскольку сумма четных чисел четна, мы заключаем, что с помощью 35 гексамино можно накрыть четное число белых квадратов и четное число черных. К сожалению, каждый прямоугольник состоит из 105 квадратов каждого цвета. Это число нечетно, поэтому прямоугольника, который можно было покрыть 35 фигурами гексамино, не существует.

«Рассмотренные задачи, – резюмирует Голомб, – заставляют сделать вывод, который относится ко всем правдоподобным рассуждениям вообще. Взяв те или иные начальные данные, мы долго и упорно пытаемся подогнать их под некоторую схему. Если это нам удается, мы считаем, что только такая схема и «соответствует фактам». В действительности же те данные, которыми мы располагаем, отражают лишь отдельные стороны прекрасного и всеобъемлющего целого. Такого рода рассуждения неоднократно встречаются в религии, политике и даже в науке. Пентамино служит примером того, как одни и те же данные с одинаковым успехом удовлетворяют многим различным схемам. Схема, на которой мы в конце концов останавливаем свой выбор, определяется не столько имеющимися в нашем распоряжении данными, сколько тем, к чему мы стремимся.

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

* * *

Читателям, которые захотят попробовать свои силы в складывании фигур из гексамино, можно предложить еще два примера (рис. 80 и 81), заимствованных из журнала «Небывалые шахматы».

Рис. 80 Фигура I для складывания из гексамино.

Рис. 81 Фигура II для складывания из гексамино.

Каждая из фигур составлена из полного набора C5 костей) гексамино. Построить же фигуры из полного набора гексамино можно лишь в том случае, если разность между числом квадратов одного и другого цвета равна 2, 6, 10, 14, 18 и 22.

Глава 13. МАТЕМАТИЧЕСКИЕ СОФИЗМЫ

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

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

Наш первый софизм чрезвычайно элементарен. Мы предпошлем ему занимательный парадокс, на примере которого великий немецкий математик Давид Гильберт любил объяснять необычные свойства наименьшего из трансфинитных чисел «алеф-нуль». Как-то раз хозяину одной великолепной гостиницы с бесконечным, но счетным числом номеров, ни один из которых не был свободен, нужно было принять нового гостя. Хозяин вышел из положения очень просто: каждого из своих постояльцев он переселил в комнату, номер которой был на единицу больше номера прежней комнаты, в результате чего обитатель n-й комнаты переехал в (n + 1) – ю и освободил для нового гостя самую первую комнату. Как может поступить хозяин, если прибудет бесконечное множество новых гостей?

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

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

 
Их было десять чудаков,
Тех спутников усталых,
Что в дверь решили постучать
Таверны «Славный малый».
– Пусти, хозяин, ночевать,
Не будешь ты в убытке,
Нам только ночку переспать,
Промокли мы до нитки.
Хозяин тем гостям был рад,
Да вот беда некстати:
Лишь девять комнат у него
И девять лишь кроватей.
– Восьми гостям я предложу
Постели честь по чести,
А двум придется ночь проспать
В одной кровати вместе.
Лишь он сказал, и сразу крик,
От гнева красны лица:
Никто из всех десятерых
Не хочет потесниться.
Как охладить страстей тех пыл,
Умерить те волненья?
Но старый плут хозяин был
И разрешил сомненья.
Двух первых путников пока,
Чтоб не судили строго,
Просил пройти он в номер «А»
И подождать немного.
Спал третий в «Б», четвертый в «В»,
В «Г» спал всю ночь наш пятый,
В «Д», «Е», «Ж», «3» нашли ночлег
С шестого по девятый.
Потом, вернувшись снова в «А»,
Где ждали его двое,
Он ключ от «И» вручить был рад
Десятому герою.
Хоть много лет с тех пор прошло,
Неясно никому,
Как смог хозяин разместить
Гостей по одному.
Иль арифметика стара,
Иль чудо перед нами,
Понять, что, как и почему,
Вы постарайтесь сами.
 

Примером более тонкого математического софизма служит следующее «алгебраическое» доказательство того, что любое число аравно меньшему числу b.

Начнем с равенства

а = b + с.

Умножив обе его части на а – b, получим

а2 – ab = ab + ac – b2 – be.

Перенесем ас в левую часть:

а2 – ab – ас = ab – b2 – be

и разложим на множители:

а(а – b – с) = b(а – b – с).

Разделив обе части равенства на а – b – с, найдем

а = b,

что и требовалось доказать.

Много неприятностей подстерегает того, кто неосторожно обращается с мнимой единицей i (квадратным корнем из -1). Об этом свидетельствует хотя бы следующее удивительное «доказательство» равенства 1 = – 1:

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

Прежде всего начертим на листке бумаги в клетку треугольник, площадь которого равна 60 клеткам (рис. 82), и разрежем его вдоль прямых, показанных на верхнем рисунке.

Рис. 82 Треугольник Керри.

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

Иначе говоря, суммарная площадь частей исходного треугольника при переворачивании уменьшилась до 58 клеток! Перевернув еще раз (лицевой стороной вверх) лишь три части исходного треугольника, мы сможем составить из всех шести частей фигуру, изображенную на рис. 82 внизу. Ее площадь равна 59 клеткам. Что-то здесь не так, это ясно, но что именно?

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

Вы рассуждаете так: «Шансы выиграть и проиграть у меня одинаковые. Выиграв, я обеднею на сумму, равную стоимости моего галстука. Проиграв, я получу более дорогой галстук. Следовательно, заключив пари, я окажусь в более выгодном положении, чем мой приятель».

Разумеется, ничто не мешает Джону рассуждать точно так же.

Могут ли обе стороны, заключившие пари, иметь преимущество друг перед другом?

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

На наружной стороне тора проведем меридиан (рис. 83, ввер-вверху). На внутренней стороне того же тора проведем параллель.

Рис. 83 Если тор вывернуть наизнанку, то кажется, что кольца, нарисованные на его поверхности, расцепляются.

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

В нашем последнем софизме, заимствованном из элементарной теории чисел, речь пойдет о сравнительных достоинствах «интересных» чисел. Разумеется, числа могут представлять интерес с различных точек зрения. Так, для Джорджа Мура, когда он писал свою знаменитую оду тридцатилетней женщине, особый интерес представляло число 30 – Мур считал, что в этом возрасте замужние женщины особенно привлекательны. Для специалиста по теории чисел число 30 представляет, по-видимому, еще больший интерес, поскольку это наибольшее из чисел, обладающих тем свойством, что все меньшие числа, не имеющие с ними общих делителей, просты. Число 15 873 также небезынтересно: если его умножить сначала на любую цифру, то есть на любое из чисел от 1 до 9, а затем на 7, то результат будет состоять из повторений выбранной для первого умножения цифры. Еще более удивительными свойствами обладает число 142 857: умножая его на числа от 1 до 6, вы будете получать циклические перестановки одних и тех же шести цифр.

Возникает вопрос: существуют ли неинтересные числа? С помощью элементарных рассуждений нетрудно доказать, что неинтересных чисел нет. Если бы скучные числа существовали, то все числа можно было бы разбить на два класса: интересные числа и неинтересные, скучные числа. Во множестве неинтересных чисел нашлось бы одно число, которое было бы наименьшим из всех неинтересных чисел. Но наименьшее из всех неинтересных чисел – это уже число само по себе интересное. Поэтому мы должны были бы изъять его из множества неинтересных чисел и перевести в другое множество.

В оставшемся множестве в свою очередь нашлось бы наименьшее число. Повторяя этот процесс достаточно долго, можно сделать интересным любое неинтересное число.

* * *

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

Подробное объяснение софизма с треугольником и некоторые другие головоломки можно найти в двух главах «Исчезновение фигур» моей книги «Математические чудеса и тайны».[25]25
  Гарднер М. Математические чудеса и тайны. – М.: Наука, 1964.


[Закрыть] Софизм с галстуком подробно разобран у М. Крайчика.[26]26
  Kraitchik M. Mathematical Recreations. – 1942.


[Закрыть]

Заключительное «доказательство» того, что неинтересных чисел не существует, вызвало следующую телеграмму читателя:

Немедленно прекратите вылавливать неинтересные числа и превращать их в интересные. Для интереса оставьте хоть одно неинтересное число!