Урок 6. Инварианты и раскраски

Математика · ~55 минут

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

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

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

Представь: фокусник высыпает на стол гору фишек, накрывает платком, что-то делает, снимает платок — и торжественно объявляет, что сумма фишек осталась прежней. Ты, конечно, не веришь и пересчитываешь. А она и правда прежняя! Только это не фокус. Это самая мощная идея сегодняшнего урока.

Дело вот в чём. Когда ты делаешь с чем-то разные действия — переставляешь, добавляешь, меняешь местами — почти всегда есть какая-то одна штука, которая упрямо остаётся одинаковой. Например, общий вес. Вот эта «всё время одинаковая штука» и называется инвариант (от латинского «invariant» — «неизменный»).

Зачем он нужен? А вот зачем. Допустим, тебя спрашивают: «Можно ли из положения A получить положение B, делая только разрешённые ходы?» Если ты найдёшь величину, которая при каждом ходе не меняется, и окажется, что в положении A она равна 5, а в положении B равна 7 — всё, ответ «нельзя!». Потому что 5 не может превратиться в 7, если эта величина вообще не меняется.

🤔 А знаешь ли ты? Чтобы доказать, что чего-то сделать нельзя, не нужно перебирать миллион вариантов ходов. Достаточно найти одну неизменную величину — и она закрывает все варианты разом. Один инвариант сильнее тысячи переборов.

Чётность — это инвариант №1. Вспомни прошлый урок про чётность. Когда кузнечик прыгает влево-вправо на 1, его расстояние от начала каждый раз меняется на 1, то есть чётность расстояния всё время «переключается». А вот другая величина — например, чётность числа сделанных прыжков плюс чётность текущего положения — может оставаться постоянной. Чётность очень удобна, потому что у неё всего два значения: «чёт» и «нечёт». Если в начале «чёт», а в конце нужно «нечёт» — значит, не получится.

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

Самая знаменитая раскраска — шахматная: клетки чёрные и белые в шашечку, соседние всегда разного цвета. Костяшка домино 1×2 всегда накрывает одну чёрную и одну белую клетку — это ключ ко многим задачам.

Но шахматной раскраской дело не ограничивается. Бывают раскраски в три цвета (по диагоналям: цвет клетки $(i,j)$ — это остаток $(i+j)$ при делении на 3), раскраски полосами (целые строки или столбцы в чередующиеся цвета), раскраски квадратами 2×2. Какую выбрать — зависит от фигурки, которой мостят. Главный принцип один: нужна такая раскраска, при которой каждая фигурка покрывает цвета поровну или строго предсказуемо. Тогда «сколько клеток какого цвета» превращается в инвариант, и если в фигуре цветов не поровну — замостить нельзя.

💡 Лайфхак: Как искать инвариант? Сделай один ход «руками» на маленьком примере и спроси себя: а что осталось прежним? Сумма? Чётность суммы? Число клеток какого-то цвета? Та величина, что выжила после хода, — твой главный подозреваемый.

✍️ Разбор примеров

Пример 1. На доске написаны числа 1, 2, 3, …, 20. За один ход разрешается стереть любые два числа и вместо них написать их сумму. Так делают, пока не останется одно число. Каким оно будет?

⏱ Попробуй сам, потом читай дальше. Подсказка: а что вообще не меняется, когда два числа превращаются в их сумму?

Как рассуждаем. Подумаем, что не меняется при ходе. Мы стираем два числа $a$ и $b$, пишем $a+b$. Сумма всех чисел на доске была какая-то $S$. После хода: мы убрали $a$ и $b$ (это $-a-b$) и добавили $a+b$. Итог: $S - a - b + (a+b) = S$. Сумма не изменилась! Значит, общая сумма — инвариант. В начале сумма $1+2+\dots+20 = \frac{20\cdot 21}{2} = 210$. Последнее оставшееся число и есть вся сумма.

Ответ: 210.

Пример 2. Те же числа 1, 2, …, 20, но теперь за ход стирают два числа и пишут их разность (из большего вычитают меньшее). В конце осталось одно число. Может ли оно быть чётным?

Как рассуждаем. Теперь сумма меняется — казалось бы, инвариант сломался. Но не спеши! Посмотрим на сумму внимательнее. Стираем $a$ и $b$, пишем $|a-b|$. Новая сумма: $S - a - b + |a-b|$. Если, скажем, $a \ge b$, то $|a-b| = a-b$, и новая сумма $= S - a - b + a - b = S - 2b$. Мы вычли $2b$ — чётное число! Значит сама сумма скачет, а вот её чётность не меняется. Вот он, спрятавшийся инвариант. Начальная сумма $210$ — чётная. Значит и в конце сумма чётная. Но в конце осталось только одно число, и оно равно сумме. Раз сумма чётная — число чётное.

Ответ: да, последнее число обязательно чётное (его чётность предопределена).

Пример 3. Можно ли замостить (полностью покрыть без наложений и без выхода за край) доску 5×5 костяшками домино 1×2?

Как рассуждаем. Сначала самый простой инвариант — количество клеток. На доске $5 \cdot 5 = 25$ клеток. Каждая костяшка закрывает ровно 2 клетки. Значит закрытых клеток всегда чётное число. А 25 — нечётное. Покрыть нечётное число клеток костяшками по 2 невозможно.

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

📌 Запомни: Прежде чем городить хитрые раскраски, проверь самое тупое: делится ли число клеток на размер фигурки? Половина задач отсеивается прямо здесь.

Пример 4. Доска 8×8, у которой вырезали две противоположные угловые клетки (например, левую верхнюю и правую нижнюю). Осталось 62 клетки. Можно ли замостить её костяшками домино 1×2?

⏱ Попробуй сам. Клеток теперь 62 — чётно, простой фокус не сработает. Что ещё можно посчитать? (Подсказка: какого цвета вырезанные углы?)

Как рассуждаем. Здесь клеток чётное число (62 = 31 костяшка), так что простой инвариант «чётность числа клеток» не мешает. Нужна шахматная раскраска. Покрасим доску в шашечку. Каждая костяшка 1×2 всегда накрывает одну белую и одну чёрную клетку — соседние клетки всегда разного цвета. Значит, чтобы замостить доску, белых и чёрных клеток должно быть поровну.

Теперь посмотрим на углы. На шахматной доске противоположные углы — одного цвета (проверь на любой доске: левый верхний и правый нижний угол одинаковые). Мы вырезали два угла одного цвета, скажем, два чёрных. Было 32 чёрных и 32 белых, стало 30 чёрных и 32 белых. Поровну не получится! А каждая костяшка требует ровно одну чёрную и одну белую. 30 костяшек закроют 30 чёрных и 30 белых, а две белые останутся бесхозными.

Ответ: нельзя — из-за неравенства цветов после шахматной раскраски.

Пример 5. Есть фигура «уголок» — тримино из 3 клеток в форме буквы Г. Можно ли замостить такими уголками квадрат 5×5? (В нём 25 клеток.)

Как рассуждаем. Сначала проверим простое: 25 клеток, каждый уголок — 3 клетки. Делится ли 25 на 3? Нет, $25 = 3\cdot 8 + 1$. Значит, целым числом уголков 25 клеток не покрыть.

Ответ: нельзя — 25 не делится на 3.

Пример 6. А теперь раскраска в полосы. Прямоугольник 6×6 хотят разрезать на «полоски» 1×4 (четыре клетки в ряд, можно класть как угодно — горизонтально или вертикально). Возможно ли это?

Как рассуждаем. Клеток $36$, и $36 = 4 \cdot 9$, делится на 4 — простой инвариант не мешает. Применим хитрую раскраску в 4 цвета по диагонали или раскраску «полосами 2×2». Сделаем так: раскрасим доску в 4 цвета, повторяя по строкам узор, но удобнее взять раскраску квадратами 2×2 в два цвета. Возьмём такую раскраску: красим клетку чёрным, если обе её координаты (номер строки и номер столбца, считая с 1) чётные, иначе белым. Посчитаем чёрные клетки: строки чётные — это 2, 4, 6 (три строки), столбцы чётные — 2, 4, 6 (три столбца), итого $3\cdot 3 = 9$ чёрных клеток.

Теперь ключевой момент: любая полоска 1×4 накрывает ровно одну чёрную клетку. Проверим. Горизонтальная полоска занимает в одной строке 4 клетки подряд по столбцам. Среди любых 4 подряд идущих столбцов ровно два чётных. Но чёрные клетки только в чётных строках. Если строка нечётная — чёрных в этой полоске 0. Хм, тогда не «ровно одна». Эта раскраска не даёт чистого инварианта, поэтому от неё откажемся — это важный урок: не всякая раскраска срабатывает, иногда первая идея не годится, и это нормально.

🤔 А знаешь ли ты? Даже у профессиональных математиков первая раскраска часто оказывается «мимо». Это не провал — это часть работы. Отбросил неудачную, взял другую. Главное — не сдаться после первой попытки.

Проверим напрямую другим способом — а можно ли вообще? Да, можно: положим 6 горизонтальных полосок не получится (6 не делится на 4 по длине строки)… Строка длины 6 = 4+2, целиком полосками 1×4 одну строку не закрыть. Но полоски можно класть и вертикально, комбинируя. На самом деле прямоугольник 6×6 полосками 1×4 замостить нельзя, и доказывается это правильной раскраской в 4 цвета по диагоналям. Раскрасим клетку с координатами $(i,j)$ цветом, равным остатку $(i+j)$ при делении на 4. Тогда любая полоска 1×4 (хоть горизонтальная, хоть вертикальная) накрывает по одной клетке каждого из 4 цветов (четыре подряд идущих остатка — это всегда все четыре остатка). Значит, для замощения клеток каждого цвета должно быть поровну — по 9. Но если аккуратно сосчитать, в квадрате 6×6 цветов получается $9, 8, 9, 10$ — не поровну! Поэтому поровну распределить полоски не выйдет.

Ответ: нельзя; и заодно мы увидели, как подбирать раскраску — иногда с первой попытки не выходит, и нужно выбрать другую.

Главное из примера 6: раскраска — это инструмент, который иногда приходится подбирать. Хорошая раскраска та, при которой каждая фигурка покрывает цвета «ровно и предсказуемо».

💡 Запомни главное

• Инвариант — величина, не меняющаяся при ходах. Если в начале и в конце она разная — переход невозможен.
• Чтобы доказать невозможность, ищи инвариант. Не нужно перебирать все ходы.
• Чётность — самый частый инвариант (всего два значения: чёт/нечёт).
• Проверь сначала самое простое: делится ли число клеток на размер фигурки.
• Шахматная раскраска: домино 1×2 всегда накрывает 1 белую + 1 чёрную → их должно быть поровну.
• Противоположные углы шахматной доски — одного цвета.
• Раскраску иногда надо подбирать: цель — чтобы каждая фигурка покрывала цвета поровну/предсказуемо.

📝 Домашнее задание

1. На доске числа 1, 2, …, 10. За ход стирают два числа и пишут их сумму. Какое число останется в конце?

2. На доске числа $1, 2, \dots, 15$. За ход стирают два и пишут их разность. Может ли последнее число оказаться нечётным? Почему?

3. Можно ли замостить доску 7×7 костяшками домино 1×2? Объясни.

4. Доску 8×8 раскрасили в шашечку. Вырезали две клетки одного и того же цвета (не обязательно углы). Можно ли утверждать, что оставшиеся 62 клетки точно нельзя замостить домино? А если вырезали две клетки разного цвета — что можно сказать?

5. На столе лежат 7 монет орлом вверх. За один ход переворачивают ровно три монеты. Можно ли за несколько ходов сделать так, чтобы все монеты лежали решкой вверх? (Подсказка: следи за чётностью числа «орлов».)

6. Прямоугольник 4×5 хотят замостить фигурками-уголками (тримино из 3 клеток). Возможно ли это? Проверь сначала делимость.

7. На доске 8×8 жук стоит в левом нижнем углу и хочет пройти по всем клеткам ровно по одному разу, переходя только на соседнюю клетку (вверх/вниз/влево/вправо), и закончить в правом верхнем углу. Возможно ли это? (Подсказка: шахматная раскраска и цвета углов.)

8. ⭐ Квадрат 10×10 хотят разрезать на полоски 1×4. Раскрась клетку $(i,j)$ цветом, равным остатку $(i+j)$ при делении на 4, и выясни, возможно ли замощение. Сосчитай, сколько клеток каждого цвета.