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

Математика

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

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

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

Вот «фокус», который легко проверить самому. Напиши на столе несколько чисел, например $3$, $5$ и $8$. Разрешён один ход: стереть любые два числа и написать вместо них их сумму. Попробуй: сотри 3 и 5, напиши 8, остались $8$ и $8$; сотри их, напиши 16, осталось $16$. Что бы ты ни стирал и в каком порядке, в конце всегда выходит 16.

Почему всегда 16? Потому что на каждом ходу сумма всех чисел на столе не меняется: мы убираем два числа и тут же возвращаем ровно столько же — их сумму. А раз в самом начале сумма была $3+5+8=16$, она и останется 16 до конца, как бы мы ни ходили.

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

Зачем вообще нужен инвариант

Допустим, тебя спрашивают: «Можно ли из положения A получить положение B, делая только разрешённые ходы?» Обычно хочется начать перебирать: сделаю такой ход, потом такой, потом эдакий… Но ходов бывают миллионы, и перебрать все невозможно.

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

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

⚠️ Важная тонкость. Инвариант доказывает только невозможность. Если в A и в B инвариант одинаковый, это ещё не значит, что переход возможен! Может, мешает что-то другое. Инвариант — это как замок на двери: если замок закрыт (значения разные), точно не пройдёшь. Но если замка нет, это ещё не гарантия, что дверь откроется.

Инвариант, который меняется по правилу

Иногда величина не стоит на месте, а меняется по понятному закону, и это тоже инвариант! Например, если при каждом ходе некое число увеличивается ровно на 2, то его чётность не меняется никогда. Само число скачет, а его чётность «застыла». Мы будем ловить именно такие «застывшие свойства».

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

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

Раскраски: способ увидеть невидимый инвариант

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

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

Почему домино всегда берёт разные цвета? Потому что клетки, которые оно накрывает, — соседние (по стороне), а у соседних по шахматной раскраске цвет всегда разный. Значит, если положить $n$ костяшек, они накроют ровно $n$ белых и $n$ чёрных клеток. Число белых равно числу чёрных — вот наш инвариант замощения домино. Если на фигуре белых и чёрных клеток не поровну, замостить домино её нельзя. Просто и безотказно.

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

Но шахматной раскраской дело не ограничивается. Под каждую фигурку подбирают свою раскраску:

• В три цвета по диагоналям. Цвет клетки $(i,j)$ — это остаток $(i+j)$ при делении на 3. Получаются цветные диагонали. Удобно для фигурок из трёх клеток в ряд.
• В четыре цвета по диагоналям. Цвет клетки $(i,j)$ — остаток $(i+j)$ при делении на 4. Любые четыре клетки подряд (по строке или столбцу) дают все четыре цвета ровно по одному разу. Идеально для полосок 1×4.
• Полосами. Целые строки (или столбцы) красят в чередующиеся цвета.
• Квадратами 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+\cdots +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$. А если $a<b$, то $|a-b|=b-a$, и новая сумма $=S-a-b+(b-a)=S-2a$. В обоих случаях мы вычли чётное число ($2b$ или $2a$)! Значит сама сумма скачет, а вот её чётность не меняется. Вот он, спрятавшийся инвариант. Начальная сумма $210$ — чётная. Значит и в конце сумма чётная. Но в конце осталось только одно число, и оно равно сумме. Раз сумма чётная, число чётное.

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

💡 Лайфхак: Если сумма «не хочет» быть инвариантом, попробуй её чётность. Очень часто меняется-то она на чётную величину, и чётность выживает. Это приём-выручалочка.

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

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

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

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

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

⏱ Попробуй сам. Клеток $36$, и $36=4\cdot 9$, на 4 делится, простой фокус не поможет. Нужна раскраска. Какая?

Как рассуждаем. Клеток $36$, и $36=4\cdot 9$, делится на 4, простой инвариант не мешает. Попробуем раскраску в 4 цвета по диагоналям: клетку с координатами $(i,j)$ красим цветом, равным остатку $(i+j)$ при делении на 4. Получатся четыре «сорта» клеток: с остатками 0, 1, 2, 3.

Ключевое свойство: любая полоска 1×4 (хоть горизонтальная, хоть вертикальная) накрывает по одной клетке каждого из 4 цветов. Почему? Возьмём горизонтальную полоску в строке $i$, столбцы $j,j+1,j+2,j+3$. Суммы $i+j,i+j+1,i+j+2,i+j+3$ — это четыре подряд идущих числа, а их остатки при делении на 4 — это всегда все четыре разных остатка $0,1,2,3$ (в каком-то порядке). Для вертикальной полоски то же самое: меняется $i$, и снова четыре подряд идущих суммы. Значит, каждая полоска берёт ровно один цвет 0, один цвет 1, один цвет 2 и один цвет 3.

Раз каждая полоска берёт по одной клетке каждого цвета, то для замощения клеток каждого цвета должно быть поровну. Полосок было бы $36:4=9$, значит каждого цвета должно быть по 9. Сосчитаем по картинке, сколько клеток какого цвета:

• цвет 0: 8 клеток,
• цвет 1: 9 клеток,
• цвет 2: 10 клеток,
• цвет 3: 9 клеток.

Всего $8+9+10+9=36$, сходится. Но поровну не получилось: цвета 0 всего 8, а цвета 2 целых 10. А для замощения нужно строго по 9 каждого. Инвариант нарушен, замостить нельзя.

Ответ: нельзя, раскраска в 4 цвета показывает, что клеток разных цветов не поровну.

⚠️ Не всякая раскраска срабатывает! Если бы мы взяли шахматную раскраску, полоска 1×4 накрывала бы 2 белые и 2 чёрные, всегда поровну, и никакого противоречия мы бы не поймали. Раскраску надо подбирать под фигурку. Для полосок 1×4 подходит именно 4-цветная по диагоналям, а шахматная бесполезна.

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

Пример 5. На столе лежат 5 монет орлом вверх. За ход переворачивают ровно две монеты. Можно ли добиться, чтобы все 5 лежали решкой вверх?

⏱ Попробуй сам. Следи за числом «орлов»: как оно меняется за один ход?

Как рассуждаем. Посчитаем число монет, лежащих орлом вверх. В начале их 5, в конце нужно 0. За один ход мы переворачиваем две монеты. Тут три случая: перевернули две «орла» (орлов стало на 2 меньше), две «решки» (орлов на 2 больше) или орла и решку (число орлов не изменилось). Во всех случаях число орлов меняется на $-2$, $+2$ или $0$, то есть на чётную величину. Значит, чётность числа орлов — инвариант. В начале орлов 5 — нечётно. В конце нужно 0 — чётно. Из нечётного чётное не получить.

Ответ: нельзя, чётность числа орлов не может измениться.

💡 Лайфхак: В задачах про монеты и переворачивания почти всегда работает чётность числа «орлов» (или «решек»). Смотри, на сколько меняется это число за один ход. Если всегда на чётное, вот и инвариант.

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

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

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

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

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

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

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

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

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

7. ⭐ Квадрат 10×10 хотят разрезать на полоски 1×4. Возможно ли это?