Урок 2. Раскраски и замощения: шахматная доска как оружие

Олимпиадная математика · ~40 минут

Домино накрывает две соседние клетки. Простая штука. Но если раскрасить доску как шахматную, домино вдруг превращается в детектор: оно всегда накрывает одну чёрную и одну белую клетку. И это крошечное наблюдение позволяет доказывать, что целые доски замостить невозможно. Раскраска — это способ спрятать инвариант в цвет.

🎯 Что ты узнаешь

• Шахматную раскраску и почему домино её «уважает»
• Как доказывать невозможность замощения через подсчёт цветов
• Раскраски не в 2, а в 3 и более цветов — для тримино и других фигур
• Как выбирать раскраску под конкретную фигуру

📖 Разбираемся в теме

Шахматная раскраска

Раскрасим доску $8\times 8$ в чёрный и белый как шахматную: соседние по стороне клетки разного цвета. Тогда чёрных клеток 32 и белых 32.

Ключевой факт: любая костяшка домино ($1\times 2$), как бы её ни положить, накрывает ровно одну чёрную и одну белую клетку. Потому что соседние клетки всегда разного цвета.

📌 Запомни: Если фигуры замощения всегда покрывают равное число клеток каждого цвета, а на доске цветов поровну не хватает — замощение невозможно.

Классика: доска без двух углов

Вырежем из доски $8\times 8$ две противоположные угловые клетки. Останется 62 клетки. Можно ли замостить их 31 костяшкой домино?

Противоположные углы шахматной доски — одного цвета (проверь: клетки $(1,1)$ и $(8,8)$ обе, скажем, чёрные). Убрав две чёрные, получим 30 чёрных и 32 белых. Но каждое домино берёт по одной клетке каждого цвета, значит 31 домино взяли бы 31 чёрную и 31 белую. А чёрных всего 30 — противоречие. Замостить нельзя. ∎

🤔 А знаешь ли ты? Эта задача называется «задача о мутированной шахматной доске» и её любят задавать на собеседованиях. Без идеи раскраски она кажется «переборной» и безнадёжной, а с раскраской решается в две строки.

Раскраски в несколько цветов

Для фигур посложнее двух цветов мало. Возьмём прямое тримино (полоска $1\times 3$). Раскрасим доску в три цвета по диагоналям — клетку $(i,j)$ красим в цвет $(i+j)\bmod 3$. Тогда любая полоска $1\times 3$ (горизонтальная или вертикальная) накрывает по одной клетке каждого из трёх цветов. Это мощный детектор для задач с тримино.

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

L-тримино и раскраска в 4 цвета / другие трюки

Не всякая фигура ведёт себя одинаково при повороте — тогда одноцветный подсчёт не срабатывает, и приходится комбинировать: раскраска + чётность, или раскрашивать не всю доску, а только «опасные» клетки.

⚠️ Раскраска доказывает только невозможность. Если раскраска «не запрещает» — это ещё не значит, что замощение существует; его нужно предъявить явно.

✍️ Разбор задачи

Задача. Можно ли замостить доску $10\times 10$ прямоугольниками $1\times 4$ (полосками из четырёх клеток, которые можно класть и горизонтально, и вертикально)?

Решение. Обычная шахматная раскраска тут бессильна: полоска $1\times 4$ всегда берёт 2 чёрные и 2 белые клетки, и никакого перекоса не возникает. Нужна более хитрая раскраска.

Раскрасим столбцы циклически в цвета $1,2,3,4,1,2,3,4,1,2$. Посчитаем, сколько клеток каждого цвета. Цвета столбцов: $1,2,3,4,1,2,3,4,1,2$ — цвет 1 в столбцах ${1,5,9}$ (3 столбца), цвет 2 в ${2,6,10}$ (3 столбца), цвет 3 в ${3,7}$ (2 столбца), цвет 4 в ${4,8}$ (2 столбца). Каждый столбец содержит 10 клеток, поэтому:

• цвет 1: $30$ клеток, цвет 2: $30$, цвет 3: $20$, цвет 4: $20$.

Горизонтальная полоска $1\times 4$ покрывает 4 столбца подряд — по одной клетке каждого из 4 цветов. Вертикальная полоска стоит в одном столбце — покрывает 4 клетки одного цвета.

Пусть в замощении $h$ горизонтальных и $v_1,v_2,v_3,v_4$ вертикальных полосок в столбцах цветов $1,2,3,4$. Клеток цвета 3 всего 20, их дают горизонтальные (по одной на каждую) и вертикальные цвета 3 (по 4): $h + 4v_3 = 20$. Аналогично цвет 4: $h + 4v_4 = 20$, цвет 1: $h + 4v_1 = 30$, цвет 2: $h + 4v_2 = 30$.

Вычтем первое из третьего: $4v_1 - 4v_3 = 10$, то есть $v_1 - v_3 = 2{,}5$ — не целое! Противоречие. Значит, замостить доску $10\times 10$ полосками $1\times 4$ невозможно. ∎

Красиво, правда? Одна хитрая раскраска столбцов — и всё разваливается на арифметику.

📝 Задачи

1. Из доски $8\times 8$ вырезали одну белую и одну чёрную клетку (произвольные). Всегда ли оставшиеся 62 клетки можно замостить 31 домино? Обоснуй (тут ответ «да» — попробуй придумать идею, почему).

2. Можно ли замостить доску $5\times 5$ костяшками домино $1\times 2$? Почему?

3. Доску $6\times 6$ замостили 18 костяшками домино. Докажи, что найдётся прямая (горизонтальная или вертикальная линия сетки), которая не пересекает ни одной костяшки. (Знаменитый факт; но сначала попробуй хотя бы для $4\times4$.)

4. Можно ли доску $8\times 8$ замостить 21 прямым тримино $1\times 3$ и одним квадратиком $1\times 1$? Если да — где может стоять квадратик? (Используй раскраску в 3 цвета.)

5. Комнату $10\times 10$ хотят выложить плитками $1\times 4$ и $2\times 2$. Осталась одна плитка $2\times 2$, а вместо неё привезли $1\times 4$. Докажи, что теперь выложить пол этими плитками нельзя (то есть заменить одну $2\times2$ на одну $1\times4$ и переложить весь пол не удастся).

6. Можно ли замостить доску $6\times 6$ уголками-тримино (L-тримино из 3 клеток)? А доску $5\times 6$?

7. На доске $8\times 8$ отметили центры всех клеток. Можно ли соединить их одной замкнутой ломаной из 64 звеньев так, чтобы каждое звено соединяло центры соседних по стороне клеток и ломаная проходила через каждый центр ровно раз? (Раскраска подскажет ответ.)

8. ⭐ Доску $2^n \times 2^n$ с одной вырезанной (любой) клеткой всегда можно замостить L-тримино (уголками из 3 клеток). Докажи это для всех $n\ge 1$. (Подсказка: индукция и деление доски на 4 четверти.)