Урок 1. Инварианты: то, что не меняется

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

Представь, что у тебя есть машина, которая переставляет фишки по хитрым правилам, и вопрос: можно ли из одной картинки получить другую? Часто ответ «нельзя», и доказать это кажется невозможным — ведь ходов бесконечно много! Но есть волшебный приём: найти величину, которая при любом ходе не меняется. Если у стартовой и целевой позиций она разная — переход невозможен. Это и есть инвариант.

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

Что такое инвариант и почему он доказывает невозможность
Как чётность становится самым частым инвариантом
Как придумывать инвариант под конкретную задачу
Чем инвариант отличается от полуинварианта (величины, которая только растёт или только убывает)

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

Идея инварианта

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

Логика такая: если инвариант в начале равен $A$, то он останется равным $A$ после любого числа ходов. Значит, любая достижимая позиция имеет тот же инвариант $A$. Поэтому:

📌 Запомни: Если у двух позиций инварианты различны — из одной в другую попасть нельзя. (Обратное неверно: равенство инвариантов не гарантирует, что переход возможен.)

Чётность — король инвариантов

Самый частый инвариант — чётность какой-нибудь суммы или количества. Почему? Потому что многие операции меняют величину на $\pm 2$, или меняют сразу две вещи, и суммарная чётность сохраняется.

💡 Прежде чем искать сложный инвариант, спроси: «А что тут сохраняет чётность?» В половине задач этого хватает.

Пример: перевороты монет

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

Инвариант — чётность числа орлов. Изначально орлов 7 (нечётно). Один ход переворачивает две монеты; число орлов при этом меняется на $+2$, $0$ или $-2$ (в зависимости от того, что было под перевёрнутыми монетами). В любом случае чётность числа орлов не меняется. Значит, орлов всегда остаётся нечётное число, и получить 0 орлов (чётное) нельзя.

⚠️ Обрати внимание: важно, что переворачиваем ровно две. Если бы разрешалось переворачивать одну или три — чётность бы менялась, и инвариант не сработал бы.

Полуинвариант

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

🤔 А знаешь ли ты? Именно полуинварианты стоят за доказательствами того, что многие «переставляющие» игры конечны — например, сортировка пузырьком: число «беспорядков» (инверсий) строго убывает с каждым обменом.

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

Задача. В строку выписаны числа $1, 2, 3, \dots, 10$. За один ход можно взять любые два соседних числа и заменить их на модуль их разности (например, соседей $3$ и $7$ заменить на $4$; строка станет короче на одно число). После девяти ходов останется одно число. Какова чётность этого числа? Может ли остаться $0$?

Решение. Ключевое наблюдение: $|a-b|$ имеет ту же чётность, что и $a+b$, потому что $a+b$ и $a-b$ отличаются на $2b$, а модуль чётность не меняет. Значит, замена пары $(a,b)$ на $|a-b|$ меняет сумму всех чисел на $(a+b) - |a-b|$ — а это чётное число. Следовательно:

Чётность суммы всех чисел — инвариант.

Начальная сумма: $1+2+\dots+10 = \frac{10\cdot 11}{2} = 55$ — нечётна. Значит, и финальное единственное число нечётно. В частности, $0$ остаться не может (ноль чётен). ∎

Заметь, чему именно равно финальное число, инвариант не говорит — только его чётность. Но для вопроса задачи этого достаточно.

📝 Задачи

На столе 5 стаканов вверх дном. За ход разрешено перевернуть ровно 4 стакана. Можно ли добиться, чтобы все стояли правильно (вверх открытой стороной)?
На доске написаны числа $1$ и $2$. За ход можно стереть два числа $a$ и $b$ и написать вместо них $a+b-1$. В конце останется одно число. Каким оно будет, если начать с чисел $1, 2, 3, \dots, 100$?
В клетках полоски $1\times n$ стоят фишки. За ход можно передвинуть любую фишку на 2 клетки влево или вправо (если клетка свободна). Изначально фишки на клетках с номерами $1, 2, 3$. Можно ли переставить их на клетки $2, 3, 4$? (Клеток достаточно много.)
Дракон имеет 100 голов. Богатырь одним взмахом меча срубает 15, 17, 20 или 5 голов, но после каждого взмаха у дракона отрастает соответственно 24, 2, 14 или 17 голов (если голов хватает, чтобы срубить). Дракон умирает, только если у него ровно $0$ голов. Сможет ли богатырь победить?
Числа $1, 2, \dots, 2026$ выписаны в ряд. За ход выбирают два числа и заменяют их суммой. Так продолжают, пока не останется одно число. Может ли оно оказаться чётным? Обоснуй.
В каждой клетке доски $8\times 8$ стоит $+1$ или $-1$. За один ход разрешается одновременно поменять знак у всех чисел в одной строке или во всём столбце. Докажи, что из позиции «все $+1$» нельзя получить позицию, где сумма всех 64 чисел равна $-2$.
По кругу расставлены 7 чисел, каждое равно $+1$ или $-1$. За ход разрешается поменять знак сразу у двух соседних чисел. Изначально стоит одно число $-1$ и шесть $+1$. Можно ли за несколько ходов сделать все числа равными $+1$? (Подсказка: следи за произведением всех семи чисел.)
⭐ На доске $8\times 8$ стоит фигура «хамелеон», которая ходит как шахматный конь. Может ли конь, стартовав с угловой клетки, обойти все 64 клетки ровно по одному разу и вернуться в исходную угловую клетку? (Подсказка: раскрась доску и подумай, какой инвариант связан с ходом коня. Ответ «да» надо подтвердить примером маршрута, «нет» — инвариантом.)