[Фрагмент статьи «Шахматные доски и полимино»]

Кlemчатые государ и полимино

А. Ю. Сойфер

Профессор Южнокалифорнийского университета С. Голомб — автор ряда работ по теории информации, теории кодирования, математической статистике и их приложения к теории математических машин и генетике. Но не эти работы, представляющие безусловный интерес для специалистов, определяли широкую популярность имен профессионального им в часы доступа игре, точнее, целой серии игра, связанных с так называемым «полимино». Голомб опубликовал в 1965 году книгу «Полимино», содержащую много красных и интересных математических задач. Часть этих и им подобных задач известна нашему читателю по недавно выSEDшей в издательстве «Мир» книге Мартина Гарднера «Математические головоломки и развлечения»* (главы 12 и 46), а также по серии публикаций в разделе «Психологический практику» журнала «Нука и жизнь» за 1967—1968 гг., где, в частности, описаны голововские игры «пентамино» и «гексатрион» и ряд связанных с ними задач.

«История» полимино начинается со статьи Голомба «Шахматные докки и полимино», который он, будучи еще аспирантом Гарвардского университета, опубликовал в 1954 году в журнале American Mathematical Monthly («Американский математический ежемесячник»). Публикуемый отрывок из этой статьи («А. М. М.», 61 № 10. Перевод И. И. Яглома), введет вас в круг основных понятий, связанных с полимино, даст примеры «типичных» задач на полимино. В идешей dalleе статьей躬дет речь о некоторых более общих задачах на ту же тему. Итак, слово С. Голомбу.

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

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

*) Издательство «Мир», М., 1971.

а n косточek домино — n светлых и n темных квадратов, то есть поровну тех и других. Но изображенная на рисунке 1 шахматная докка содержит большие темных клеток, чем светлых. Поэтому ее и нельзя покрыть косточками домино.

Мы по-прежнему будем использовать в качестве «игрового поля» общную шахматную докку размера 8 × 8, но обобщим домино в «полимино» — и наши теоремы охватят все простейшие типы полимино, изображенные на рисунке 2. Более точно: мы определим n-mino как совокупность n квадратов шахматной докки, группированных «по принципу ладьи», то есть так, что поставленная на любую клетку n-mino ладья может

За конечное число ходов перейти на любую другую клетку того же $n$-мино.

Сначала мы рассмотрим тримино. Ясно, что шахматную доску размета $8 \times 8$ нельзя покрыть тримино, так как 64 не делится на 3. Попытаемся вместе этого покрыть шахматную доску 21-м тримино и одним мономино.

Шахматную доску нельзя покрыть 21-м примым тримино и одним мономино, расположенным в верхнем левом углу доски. Чтобы доказать это, мы раскраим теперь доску в три цвета: $a$, $b$ и $c$ (рис. 3). Как видите, у нас получилось 21 поле цвета $a$, 22 поля цвета $b$ и 21 поле цвета $c$. Каждый примео тримино покрывает одно поле цвета $a$, одно поле цвета $b$ и одно поле цвета $c$, то есть примыте тримино всегда покрывают одинаковое число $a$-клеток, $b$-клеток, и $c$-клеток. Верхний левый угол — это $a$-клетка и после покрытия ее мономино у нас останутся неравные количество $a$-, $b$- и $c$-клеток. Следовательно, покрыть оставшиеся 63 клетки примым тримино невозможно.

Точно так же мы убеждаемся, что после покрытия мономино любой $a$-или $c$-клетки оставшуюся часть доски нельзя покрыть примым тримино. Остается рассмотреть лишь $b$-клетки. Но если мономино покрывается, например, $b$-клетки, расположенную в нижнем левом углу, то в силу симметрики доски относительно изображенной на рисунке 3 примой $x$ мы приходим к уже рассмотренной задаче покрытия примым тримино доски, в верхнем левом углу которого лежит мономино. Верхний левый угол доски — это $a$-клетка, и в этом случае покрытие невозможно; значит, оно невозможно и тогда, когда мономино лежит в нижнем левом углу.

Таким образом, установливается, что для того, чтобы покрытие было возможно, мономино должно покрывать непреемно такую $b$-клетку, которая относительно примых $x$ и $y$ (см. рис. 3). симметрина также $b$-клеткам. Единственные такие клетки

4

Рис. 4. Рис. 5.

Рис. 6.

Рис. 7.

ки — это те, что закрашены на рисунке 4. А из рисунка 5 следует, что если мономино покрывает одну из этих клеток, то оставшуюся часть мономино действительное можно покрыть прямыми тримино.

Итак, необходимо и достаточно условия возникности покрытия шахматной мономино и 21-м прямым тримино состоящим в том, что мономино покрывает одну из закрашенных на рисунке 4 клеток.

До сих пор мы имели дело с «доказательствами невозможности». Следующий результат имеет противоположный характер: неависимо от мою, какую клетку шахматной мономино, оставшиеся клетки моут быть покрыты 21-м прямоульным тримино.

Доказательство проводится по иndу кци и для шахматной моноки «общего вида» размером $2^n \times 2^n$. Для моноки $2 \times 2$ ясно, что где бы ни лежало на ней мономино, оставшиеся три клетки можно покрыть прямоульным тримино (рис. 6, а). Взяв теперь моноку размером $4 \times 4$, мы разделим ее на четыре части, размером каждой $2 \times 2$ (рис. 6, б). Пусть мономино покрывает клетку, скажем, желтой части на рисунке 6, б. Так как каждая четверть моноки — это дока размера $2 \times 2$, то ее можно покрыть одним тримино и одним мономино, покрывающим произвольную клетку этой моноки. В желтой части мономино уже есть; что же касается остальных трех четвертей, то мы расположим на них мономино в центральных (для большой моноки) клетках — после этого мы сможем заменить наш мономино на одно прямоульное тримино (см. тот же рисунок 6, б). Итак, мы покрыли шахматную моноку размером $4 \times 4$ одним (произвольно расположенным) мономино и пятую прямоульными тримино.

Случай моноки $8 \times 8$, как и самый общий случай, рассматривается аналогично (см. рисунок 6, в).

Теперь перейдем к террамino. Шахматную моноку легко полностью покрыть прямыми, квадратными, Г-терминно или Г-терминно — это ясно из рисунка 7. С другой стороны, покрыть моноку космитерминно невозможно — ведь косые террамino невозможно расположить на доке даже так, чтобы полностью покрыть ряд клеток, прямыхкающих к какой-либо стороне моноки…

5

Продолжим занятие полимного, начатьые знакомством со статей профессора Голомба.

Вы уже видели, что некоторые задачи на полимно во все не предполагают непреемно, что речь идет о «стандартий» шахматной доске $8 \times 8$; мы рассматривали и доски $2^n \times 2^n$ для произвольного натурального числа $n$. Так пондем теперь дальше и будем говорить о произвольных квадратных дорах $n \times n$ и, более того, о произвольных прямогольных дорах $m \times n$.

Задача 1. Наименование таких пары натуральных чисел $(m, n)$, что клематную доску $m \times n$ можно было бы выполить линейным $k$-мино.

1-й способ решения.

Если хотя бы одно из чисел $m, n$ делится на $k$, то доску $m \times n$ можно выполить линейным $k$-мино (проверте!).

Предположим, что ни одно из чисел $m, n$ не делится на $k$, а доска $m \times n$ тем не менее уложена линейным $k$-мино. Раскрасием доску $k$ цветами диагональным способом, циклические меняя цвета: 1-й, 2-й, …, $k$-й, 1-й, 2-й, … (рис. 8).

Раскрашенная таким способом доска имеет интересное свойство: как бы на ней ни было расположено линейное $k$-мино, горизонтальное или вертикальное, оно покрываетровно по одной клетке каждой из $k$ цветов. Итак, по предположению доска покрыта линейным $k$-мино, а каждое $k$-мино покрывает одинаковое число клеток каждой цвета (по одной клетке)

Рис. 8. Диагональная раскраска при $k=3$.

6

равные количество клеток каждой цвета.

Но, с другой стороны, цветных диагоналей в такой доске всегда

$$r_2 + r_1 - 1 \leq \frac{k}{2} + \frac{k}{2} - 1 < k,$$

так что в ней не будет ни одной клетки хотя бы одного из употребленных для раскраски цветов. Противоречие!

Итак, доску $m \times n$ можно выложить линейным $k$-minо тогда и только тогда, когда хотя бы одно из чисел $m, n$ делится на $k$.

Эту задачу можно решить, используя инную раскраску.

2-й способ решения.

Предположим, что ни одно из чисел $m, n$ не делится на $k$, а доска $m \times n$ выложена линейным $k$-minо.

Разделим с остатком $m$ и $n$ на $k$:

$$m = kq_1 + r_1; \quad 0 < r_1 < k,$$
$$n = kq_2 + r_2; \quad 0 < r_2 < k.$$

Раскрасием доску $k$ цветами следующим образом: 1-й столбец — 1-м цветом, 2-й — 2-м, …, $k$-й — $k$-м, $(k+1)$-й — 1-м и т. д., $m$-й — $r_1$-м цветом (рис. 9).

Раскрашения таким способом доска имеет следующое свойство: если линейное $k$-minо положить на доску вертикально, то оно будет покрывать $k$ клеток одного цвета, а если горизонтально — торовно по одной клетке каждой цвета. Доска, по предположению, выложена $k$-minо; поэтому

$$S_1 \equiv S_2 \equiv \dots \equiv S_k \pmod{k},$$

где $S_1(l=1, 2, \dots, k)$ есть число

Рис. 9. Столбцевая раскраска при $k=4$.

клеток $l$-го цвета, содержащихся в доске.

С другой стороны, как легко подсчитать,

$$S_{r_1} - S_{r_1+1} = n;$$

следовать,

$$S_{r_1} - S_{r_1+1} \equiv r_2 \pmod{k},$$

так что

$$S_{r_1} \neq S_{r_1+1} \pmod{k}.$$

Полученное противоречие показывает, что для существования искомой укладки необходимо $m: k$ или $k^*$).

Уж не подумали ли вы, что решения задач об укладке доски полимно не прееменно связано с тем или иным способом раскрашивания доски? Ничего подобного!

3-й способ решения.

Предположим, что доска $m \times n$ выложена линейным $k$-minо и

$$m = kq + r_1; \quad 0 < r_1 < k;$$
$$n \equiv r_2 \pmod{k}; \quad 0 < r_2 < k.$$

Будем говорить, что $k$-minо «растет из $l$-го столбца», если оно расположено горизонтально и начинается в $l$-м столбце (рис. 10).

Обозначим через $t_l$ количество $k$-minо, растущих из $l$-го столбца. По предположению доска выложена $k$-minо; поэтому

$$t_1 \equiv r_2 \pmod{k},$$
$$t_2 \equiv 0 \pmod{k},$$
$$t_3 \equiv 0 \pmod{k},$$
$$\dots$$
$$t_k \equiv 0 \pmod{k},$$
$$t_{k+1} \equiv r_2 \pmod{k},$$
$$t_{k+2} \equiv 0 \pmod{k},$$
$$\dots$$
$$t_{kq+1} \equiv r_2 \pmod{k}.$$

*) $m: k$, как обычно,означет, что $m$ делится на $k$.

Рис. 11.

С другой стороны, ясно, что $k$-мино, растущее из $(kq+1)$-го столбца, «вырастет» за пределы прямогольника, откуда $t_{kq+1} = 0$. Мы и здесь пришли к противоречию, показывающему, что для существования укладки доски $m \times n$ $k$-мино необходима делимость хотя бы одного из чисел $m, n$ на $k$.

Для дальнейших задач нам понадобится «система координат» на доске, мы занутером строки и столбцы доски (см. рис. 11).

Каждая клетка теперь задается парой чисел $(x, y)$, где $x$ и $y$ — соответственно номера строки и столбца, в которых эта клетка расположена.

Задача 2. Имеется прямогольная клетчатая доска $m \times n$ и линейное $k$-мино. Клетку доски $(x, y)$ будем называть «удачно расположенной», если фигуру $F$, получающей из доски в результате вырезания этой клетки, можно выполнить линейным $k$-мино. Наименование $M$ всех удачно расположенных клеток доски.

При $k = 1$, очевидно, $M$ совпадает с множеством всех клеток доски. Допустим, что $k = 2$. Предположим, что из прямогольника вырезана одна клетка и полученная фигура $F$ выложена домино; тогда $(mn-1)$ —

Рис. 12.

Рис. 13.

Рис. 14.

клеток $(x, y)$, что $x \equiv y$ (mod 2); если хотя бы одно из чисел $m, n$ кратно 2, то доска $m \times n$ удачно расположенных клеток не имеет.

Пусть теперь $k > 2$. В этом случае $1 \neq -1$ (mod $k$).

Предположим, что полученная последвая вырезания клетки $(x, y)$ фигура $F$ уложена линейным $k$-мино. Устройм на данной доске столбцевую циклическую раскраску в $k$ цветов (см. рис. 9). Мы уже отмечали свойство доски, раскрашенной таким способом: если линейное $k$-мино расположено на доске вертикально, то оно покрывает $k$-клеток одного цвета, а если горизонтально, торовно по одной клетке каждой цвета. По предположению, фигура $F$ выложена линейным $k$-мино; поэтому

$$P_1 \equiv P_2 \equiv \dots \equiv P_k \pmod{k},$$

(1) где $P_l (l = 1, 2, \dots, k)$ — количество клеток $l$-го цвета в фигуре $F$.

Пусть

$$m = kq_1 + r_1 \quad (0 \leqslant r_1 < k),$$
$$n = kq_2 + r_2 \quad (0 \leqslant r_2 < k).$$

Обозначим через $S_l (l = 1, 2, \dots, k)$ число клеток $l$-го цвета во всей доске. Легко подсчитать, что

$$S_1 = \dots = S_{r_1} = n(q + 1),$$

(2a)
$$S_{r_1+1} = \dots = S_k = nq.$$

Фигура $F$ содержитровно на одну клетку меньше, чем все доска, поэтому из соответствия (1) и (2) следует, что возможность лишь два слуая: либо $r_1 = 1$ и вырезанная клетка — первого цвета, либо $r_1 + 1 = k$ и вырезанная клетка — $k$-го цвета.

1 слуай. Вырезанная клетка $(x, y)$ — первого цвета, то есть $y \equiv 1 \pmod{k}, r_1 = 1, m \equiv 1 \pmod{k}$, и кроме того,

$$S_1 - 1 \equiv S_2 \equiv S_3 \equiv \dots \equiv S_k \pmod{k},$$

откуда $n(q + 1) - 1 \equiv nq$. (mod $k$), то есть $n \equiv 1 \pmod{k}$.

Итак, $m \equiv n \equiv y \equiv 1 \pmod{k}$.

2 слуай. Вырезанная клетка $(x, y)$ — $k$-го цвета, то есть $y \equiv 0 \pmod{k}, r_1 = k - 1,$

$$m \equiv -1 \pmod{k}$$ и, кроме того,

$$S_1 \equiv S_2 \equiv \dots \equiv S_{k-1} \equiv S_k - 1 \pmod{k},$$

откуда $nq - 1 \equiv n(q + 1) \pmod{k}$, то есть $n \equiv -1 \pmod{k}$.

Итак,

$$m \equiv n \equiv -1 \pmod{k}; y \equiv 0 \pmod{k}.$$

Повернем теперь данную доску на $90^\circ$, то есть рассмотрим доску $n \times m$ и применим к ней изложенные выше рассудения. Вот окончательные выводы: если $m \equiv n \equiv 1 \pmod{k}$, то координаты удалено расположенной клетки $(x, y)$ должны удовлетворять соответствию $x \equiv y \equiv 1 \pmod{k}$. Если же $m \equiv n \equiv -1 \pmod{k}$, то координаты удалено расположенной клетки $(x, y)$ должны удовлетворять соответствию $x \equiv y \equiv 0 \pmod{k}$.

$x \equiv y \equiv 0 \pmod{k}$.

В остальных случаях удалено расположенных клеток доска $m \times n$ не имеет.

Рисунки 15 и 16 показывают, что если $m \equiv n \equiv 1 \pmod{k}$, то любая клетка

9

ка $(x, y)$, для которого $x \equiv y \equiv 1$ (mod $k$), удачно расположена; если же $m \equiv n \equiv -1$ (mod $k$), то удачно расположена любая клетка $(x, y)$, для которой $x \equiv y \equiv 0$ (mod $k$).

Итак, задача решения.

Ответ удобно записать в виде таблицы (см. таблицу сверху).

Мы видим, что если доска $m \times n$, при $k > 2$ и содержит удачно расположенные клетки, то их количество $v$ сравнительно с числом всех клеток доски невелико; докажите, что

$$v = \frac{[m + (-1)^r(k - 1)][n + (-1)^r(k - 1)]}{k^2},$$

где $r = 1$, если $m \equiv n \equiv 1$ (mod $k$), и $r = -1$, если $m \equiv n \equiv -1$ (mod $k$).

Но число таких клеток можно увеличить! Скленем пару противоположных сторон нашей доски: мы получим клетчатый цилиндр (рис. 17).

Задча 3.
a) Из прямоеольной клетчатой доски $m \times n$ склеили цилиндр. Наимножество всех удачно расположен-

ных клеток цилиндра для линейного $k$-мино.

b) Если $m \neq n$, то в зависимости от мою, какую пару противоположных сторон мы склеили, можно получить два различных цилиндра. Какой из этих цилиндров имеет большее число удачно расположенных клеток?

Пойдем теперь дальней и склеим основания нашего цилиндра (рис. 18).

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

Торидальная клетчатая доска имеет и другие достоинства. Решим, к примеру, следующую задачу.

Задча 4.
a) Найти все такие натуральные числа $n$, что квадратную доску $n \times n$ можно уложить прямоеольным прямоугольником, изображенным на рисунке 19.

Рис. 17.
Рис. 18.

10

Рис. 19, 20, 21.

6. Наими все также намуральные числа $n$, что мородальную доску, полученную из квадратной клеткой доски $n \times n$, можно выложить тримино, изобразенным на рисунке 19.

Так как тримино состоит из трех клеток, то для возникности укладки доски $n \times n$ тримино необходимо, чтобы $n$ было кратно 3.

Примугольник размером $2 \times 3$, конечно, можно уложить тримино (рис. 20). Сложнее уложить примугольник размером $5 \times 9$ (рис. 21). Теперь не представляется большого труда доказать (доказите!), что квадрат $n \times n$ можно уложить тримино при $n = 3k$, где $k = 2, 3, \dots$.

Докажите, что квадрат $3 \times 3$ нельзя уложить нашим тримино. Что же касается торидальной доски, склеенной из квадрата $n \times n$, то ее можно уложить тримино при любом $n$, делящемся на 3.

Рис. 22.

Для доказательства этого факта нам осталось показать, что торидальный доску $3 \times 3$ можно уложить тримино. Рисунок 22 показывает возможные такой укладки (при склеивания тора красные клетки соберутся, образовав тримино требуемого вида).

Уражнения

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

2. Имеется примугольная клетчатая доска $m \times n$ и натуральное число $k$, $k < \frac{mn}{2}$.

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

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

3. a) Наими все также намуральные числа $n$, что квадратную клетку доску $n \times n$ можно уложить Т-метрамно (см. рис. 2).

6. Изменится ли результат, если вместе лоскоций доски укладываются цилиндрическую? мородальную?

4. a) Наими все также намуральные числа $n$, что квадратную клетку доску $n \times n$ можно уложить Г-метрамно.

6. Изменится ли результат, если вместе лоскоций доски укладываются цилиндрическую? мородальную?

5. a) Из примугольной клеткой доски $m \times n$ склеили цилиндр. При каком условия его можно уложить линейным к-мино?

6. Если $m \neq n$, то из доски $m \times n$ можно склеить два различных листа Мёбиуса. Можно ли случиться так, что один из них можно уложить линейным к-мино, а другой — нет?

Рис. 23.

6. Примугольную доску (на коморой клетчатая семка имеется с обеих строком) перегнути и склеили, как показано на рисунке 23. Получается лист Мёбиуса.

a) При каком условия лист Мёбиуса, склеенный из доски $m \times n$, можно уложить линейным к-мино?

6. Если $m \neq n$, то из доски $m \times n$ можно склеить два различных листа Мёбиуса. Можно ли случиться так, что один из них можно уложить линейным к-мино, а другой — нет?