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

Гарднер Мартин

Рис. 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.