F11 Разрезания и замощения

Метод состоит в том, что мы анализируем задачи о покрытии или разрезании фигур, ища инварианты — свойства, которые не меняются при любом допустимом замощении, или которые допустимое замощение обязано выполнять.

Задачи на замощение — одни из самых коварных на ВсОШ: внешне кажется, что нужно просто «сложить пазл», но на самом деле либо замощение невозможно (и надо доказать это через инвариант), либо возможно (и надо конструктивно построить).

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

Интуиция: представь, что ты пытаешься разрезать пирог на ровные куски, но у пирога нечётная площадь и куски все чётной площади — явное противоречие. Раскраска — это обобщение этой идеи на случай, когда «неправильное соотношение» не видно сразу.

Второй важный инструмент — инвариант чётности площадей или координат, а также телескопические аргументы об инвариантах периметра.

• Необходимое условие замощения: если фигура $F$ замощается плитками вида $T$, то $|F|$ делится на $|T|$, где $|\cdot|$ — площадь (число клеток). Условие: плитки без перекрытий, без выхода за границу. Когда использовать: первая проверка возможности замощения.

• Принцип раскраски (двухцветный): покрась доску в чёрный и белый по правилу шахматной раски (или иному). Каждая плитка накрывает фиксированное число чёрных и белых клеток. Если у доски число чёрных $\neq$ числу белых клеток, а плитка накрывает по одной каждого цвета, замощение невозможно. Когда использовать: домино, тромино, L-образные плитки.

• Многоцветная раскраска: для плиток $1\times k$ красить столбцы (или строки) в цвета $0, 1, \ldots, k-1$ по модулю $k$. Каждая плитка накрывает ровно по одной клетке каждого цвета. Когда использовать: плитки вида $1\times 3$, $1\times 4$ или их обороты.

• Инвариант суммы координат: для домино на клетчатой доске, если клетке $(i,j)$ приписать вес $(-1)^{i+j}$, то суммарный вес каждого домино равен нулю. Если вес доски ненулевой — замощения нет.

• Конструктивное замощение: если инвариант не запрещает, строй замощение рекурсивно (например, «L-тромино» замощает $2^n\times 2^n$ квадрат с одной убранной клеткой).

• Проверить делимость площадей. Первым делом посчитай площадь фигуры и плитки. Если не делится — замощения нет.

• Раскрасить шахматно и сравнить числа чёрных и белых клеток. Для домино необходимо равенство; посчитай за 10 секунд.

• Придумать многоцветную раскраску под конкретную плитку. Для $1\times 3$ — три цвета; найти такой способ раскраски, что каждая плитка накрывает ровно по одной клетке каждого цвета.

• Использовать периметр или граничные аргументы. Если плитка всегда добавляет/убирает чётное число к периметру, а у фигуры периметр нечётный — противоречие.

• Доказать от противного через инвариант. Предположи, что замощение существует, выведи нарушение инварианта.

• Построить конструктивное замощение индукцией. Докажи для малого случая, затем покажи, как добавить следующий «слой».

• Разбить на блоки. Часто фигуру можно разбить на более мелкие части, каждая из которых независимо замощается.

Поверхностные признаки (что буквально написано):
- «Можно ли замостить ...» или «Докажите, что нельзя замостить ...».
- «Разрежьте фигуру на ... одинаковых частей».
- Упоминается клетчатая доска, домино, тримино, или плитка $1\times k$.

Структурные признаки (форма выражения, объекты):
- Площадь «целевой» фигуры делится на площадь плитки, но задача всё равно спрашивает «можно ли» — значит, скорее всего, есть тонкий инвариант.
- Фигура несимметрична или имеет «вырезанные» углы.
- Плитка сама несимметрична (L-форма, S-форма) — раскраска помогает.

Цель задачи (что от тебя хотят):
- Доказать невозможность замощения (нужен инвариант).
- Построить замощение (нужна конструкция).
- Найти, при каких условиях замощение существует.

Задача 1. Можно ли замостить прямоугольник $10\times 10$ с вырезанными противоположными угловыми клетками доминошками $1\times 2$?

Источник: классическая задача, широко известна как «задача о доминошках», тренировочная.

Как думать (рассуждение ученика):
1. Вижу: доминошки $1\times 2$ и нестандартную доску. Площадь доски = $100 - 2 = 98$ клеток, доминошка = 2 клетки, $98/2 = 49$ — делится, значит по площади всё нормально. Это НЕ доказательство возможности.
2. Помню триггер: «шахматная раскраска для домино». Крашу доску в чёрный и белый цвет.
3. На доске $10\times 10$ клеток 50 чёрных и 50 белых. Но вырезанные угловые клетки — одного цвета (у шахматной доски два противоположных угла одинакового цвета). Значит, осталось 48 клеток одного цвета и 50 другого.
4. Каждое домино накрывает ровно одну чёрную и одну белую клетку. Значит, при любом замощении число чёрных = числу белых — противоречие!

Решение:

Покрасим доску $10\times 10$ в шахматном порядке. Клетка $(i,j)$ чёрная, если $i+j$ чётно. Противоположные угловые клетки $(1,1)$ и $(10,10)$ имеют $i+j = 2$ и $i+j=20$ — оба чётны, то есть обе чёрные. После удаления: 48 чёрных, 50 белых клеток.

Любое домино накрывает ровно одну чёрную и одну белую клетку (оно лежит на двух соседних клетках, а соседние клетки всегда разного цвета). Значит, любое покрытие доминошками покрывает равное число чёрных и белых клеток. Поскольку 48 ≠ 50, замощение невозможно.

Ответ: нельзя.

Что в этой задаче было главным: раскраска превращает геометрическую невозможность в арифметическое противоречие — вот в чём сила метода.

Задача 2. Докажите, что квадрат $2^n\times 2^n$ с одной произвольно вырезанной клеткой можно замостить L-тромино (уголками $2\times 2$ с одной вырезанной угловой клеткой).

Источник: классическая задача (ВсОШ-стиль), тренировочная.

Как думать (рассуждение ученика):
1. Вижу: нужно построить замощение. Площадь $2^n\times 2^n - 1 = 4^n - 1$. Тромино занимает 3 клетки, $4^n - 1 \equiv 0 \pmod{3}$? Нет, $4^n \equiv 1^n = 1 \pmod 3$, то есть $4^n - 1 \equiv 0$ — делится. Площадная проверка прошла.
2. Идея конструктивного доказательства: разобью квадрат на 4 части $2^{n-1}\times 2^{n-1}$. В одном квадранте есть вырезанная клетка; остальным трём дам по одной «вырезанной» клетке в углах, смежных с центром — и всё это покрывается одним L-тромино в центре!
3. Это индукция.

Решение:

Докажем индукцией по $n$.

База: $n=1$, квадрат $2\times 2$ с одной вырезанной клеткой — это и есть L-тромино.

Шаг: разобьём $2^n\times 2^n$ на четыре квадранта размером $2^{n-1}\times 2^{n-1}$. Вырезанная клетка лежит в одном из них. Поставим один L-тромино в центр доски так, чтобы он покрыл по одной угловой клетке трёх оставшихся квадрантов. Теперь каждый квадрант — это $2^{n-1}\times 2^{n-1}$ с одной вырезанной клеткой. По предположению индукции, каждый замощается. Шаг доказан.

Ответ: замощение существует для любого $n\geq 1$ и любой вырезанной клетки.

Что в этой задаче было главным: рекурсивное разбиение + «хирургическая вставка» одного тромино в центр — это и есть конструктивная идея метода.

• Ошибка: проверить только делимость площадей и объявить замощение возможным. Делимость площади — необходимое, но не достаточное условие. → Всегда ищи инвариант (раскраску) прежде чем конструировать.

• Ошибка: неправильно выбрать раскраску. Выбрать шахматную раскраску для плитки $1\times 3$, где каждое домино накрывает 1 чёрную и 2 белые. → Для $1\times 3$ нужна трёхцветная раскраска колонок по $\mod 3$.

• Ошибка: забыть проверить, что плитка накрывает фиксированное число клеток каждого цвета. Сначала проверяй это свойство для выбранной раскраски и конкретной плитки.

• Ошибка: при конструктивном доказательстве не проверить граничные случаи. Индукция может сломаться на базе ($n=1$) или при нестандартном расположении вырезанной клетки.

• Ошибка: считать, что ответ «нельзя» всегда доказывается раскраской. Иногда инвариант другой (чётность периметра, сумма координат). → Если стандартная раскраска не даёт противоречия, ищи другой инвариант.

• Ошибка: не указать, как именно расположить плитки при конструктивном ответе. Простое «разобьём на части» без явного описания расположения не является доказательством. → Опиши конструкцию или нарисуй для малого $n$.