Когда ты была рыбкой, головастиком - я...

Менее известна связанная с ней другая задача. Предположим, доску изуродовали, удалив две клетки разногоцвета из любых мест доски. Всегда ли можно будет покрыть при помощи костяшек домино оставшиеся 62 клетки? Ответ — да, и существует прелестное доказательство, полученное Ральфом Гомори [72] .

_{Рис. 1. Доказательство Гомори}

<

72

М. Gardner, «The Eight Queens and Chessboard Divisions», in The Unexpected Hanging and Other Mathematical Diversions (Chicago: University of Chicago Press, 1991).

empty-line />

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

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

Если вместо пластинок домино покрывать доску с помощью L-тримино (называемых также косыми, или V-тримино, или угловыми тримино), тогда все квадратные доски, у которых число клеток без остатка делится на 3, можно будет покрыть такими фигурами (кроме доски 3x3). Среди них мы не будем рассматривать «неповрежденные», а возьмем лишь такие изуродованные доски, где число клеток кратно 3 после того, как из произвольного места доски удалили одну клетку. Будем называть такие доски дефицитными.Иными словами, доска со стороной n является дефицитной, если n ²–1 кратно 3; т. е. само n некратно 3. Длины сторон таких досок образуют ряд (1):

2, 4, 5, 7, 8, 10, 11, 13, 14… (1)

Каждое из этих чисел будем называть порядкомдоски. И еще: здесь и далее слово «тримино» будет означать исключительно L-тримино.

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

Степени двойки

Рассмотрим доску второго порядка. Ее можно покрыть, какую бы клетку мы ни удалили (см. рис. 2, слева). На рис. 2, справа, показано, как можно покрыть доску 4-го порядка. Вырезанная клетка неизбежно оказывается в квадрате 2x2, в каком-то из его четырех углов. Остальная часть доски покрывается благодаря приему, который Соломон Голомб окрестил rep-tile («рептилия»): элемент покрытия (tile) как бы воспроизводит увеличенную копию (replica) самого себя. Левый верхний квадрат 2x2 можно поворачивать, чтобы недостающая клетка оказывалась в четырех разных местах, и весь квадрат 4-го порядка можно при этом поворачивать так, чтобы эта клетка попадала на любое из его шестнадцати полей.

_{Рис. 2. Порядки 2 и 4}

А 1953 году Голомб, «отец» полимино (он придумал для них название и первым начал изучать их), вывел индуктивное доказательство, продемонстрировав, что все доски со сторонами, отвечающими прогрессии 2, 4, 8, 16…) можно покрыть с помощью тримино, когда отсутствует произвольная клетка доски. Впервые доказательство было опубликовано в 1938 году [73] . Позже его повторил Э.Б. Эскотт (см. статью в журнале «Open Court» [74] ). С тех пор математики включают это доказательство в свои книги, часто без ссылки на Голомба. Роджер Нельсен приводит Голомбово доказательство в виде единственной диаграммы, без всяких словесных пояснений [75] . Знаменитое доказательство Голомба начинается с рассмотрения квадрата 2x2 (рис. 3, слева). Этот квадрат затем помещается в угол квадрата 4—го порядка (рис. 3, в центре). А уже этот квадрат 4x4 располагается в углу квадрата 8-го порядка (рис. 3, справа), после чего рядом с углом зачерненного квадрата 4-го порядка укладывают одно тримино. Мы уже знаем, что зачерненный квадрат можно покрыть при отсутствии в нем любой клетки, и мы знаем, что три незачерненных области (примыкающих к нашему одиночному тримино) можно покрыть с помощью тримино, так как в каждой из них отсутствует одна клетка (угловая). Поворачивая доску [76] , можно добиться того, чтобы любая клетка в зачерненном квадрате приходилась на любое место доски 8-го порядка.

73

S.W. Golomb, «Checker boards and polyominoes», American Mathematical Monthly 61: 675–682, 1954.

74

S.W. Golomb, Polyominoes (New York: Scribner, 1965).

75

R.Nelsen, Proofs Without Words II: More Exercises in Visual Thinking (Washington, D.C.: Mathematical Association of America, 2000).

76

При этом недостающая клетка может находиться в любом месте квадрата 4-го порядка (аналогично рассмотренному выше случаю с досками 2 и 4-го порядка).

_{Рис. 3. Голомбово индуктивное доказательство}

Порядки 5 и 7

Далее нас ждет доска 5-го порядка, поскольку 5 — следующее число в последовательности (1), для которого мы пока не вывели доказательства. Если убрать центральную клетку, полученную фигуру можно покрыть очень аккуратно и симметрично (как показано на рис. 4. слева). Я покрыл эту доску четырьмя элементами 2x3. Каждый из них можно в свою очередь двумя различными способами покрыть двумя тримино. Покрытия 2x3 — очень полезный инструмент при решении задач с тримино. Когда недостающая клетка расположена, как показано черным на рис. 4 (средний квадрат), клетку над ней, как нетрудно убедиться, приходится покрывать с помощью тримино, примыкающего слева или справа. В любом случае у нас появятся две свободное клетки (они обозначены как 1 и 2), которые нельзя покрыть тримино. И в самом деле, квадрат 5-го порядка можно покрыть тримино, только если недостающая клетка находится в одной из позиций, обозначенных черным на рис. 4. справа. Вот вам приятное упражнение: посмотрите, удастся ли вам покрыть доску, если вырезанная клетка находится в углу.

_{Рис. 4. Квадрат 5-го порядка}

Доску 7-го порядка анализировать гораздо труднее. Я не сумел придумать одиночную диаграмму, которая доказывала бы, что такую доску можно покрыть тримино, однако Голомб прислал мне свое неопубликованное доказательство, где он использует три диаграммы.

_{Рис. 5. Квадрат 7-го порядка можно покрыть тримино (доказательство Голомба)}

Его доказательство развивается так. На рис. 5 показаны три способа покрытия доски 7-го порядка. Очевидно, что при каждом таком покрытии квадрат 2x2 можно покрыть с помощью тримино, если недостающая клетка находится в любом из его четырех углов. Поворачивая эти три фигуры, можно добиться того, чтобы недостающая клетка приходилась на любое место доски.

Несколько труднее придумать, как покрыть доски с помощью максимального количества элементов 2x3. Вот вам задачка: сможете ли вы покрыть доску 7x7 с помощью шести элементов 2x3 и четырех тримино (рис. 6)? Решение — единственное (если не считать его зеркального отражения). (Это решение приводится на с. 204).

_{Рис. 6. Задача}

Посмотрев на рис. 5, можно отметить, что для каждого приведенного разбиения количество свободных тримино (не входящих в элементы 2x3) оказывается четным. И это не совпадение. Мне удалось вывести следующий тривиальный закончик. Когда порядок доски — четный, количество свободных тримино при покрытии — нечетное, и наоборот: когда порядок доски — нечетный, число свободных тримино должно быть четным.

Доказать эти равенства просто. Если доска имеет четный порядок, то после удаления одной клетки количество тримино при любом способе покрытия составит величину, равную (n ²–1)/3, т. е. нечетное число. В каждом элементе 2x3 содержится два тримино, а значит, общее количество тримино, входящих в состав элементов 2x3, неминуемо окажется четным. Если вычесть это четное число из общего числа тримино (а оно — нечетное), мы получим нечетное число тримино, не входящих ни в один элемент 2x3.