Клетчатые доски и полимино

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$.

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$ можно склеить два различных листа Мёбиуса. Можно ли случиться так, что один из них можно уложить линейным к-мино, а другой — нет?