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

Олимпиадная математика

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

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

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

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

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

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

Логика такая: если инвариант в начале равен $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$ отличаются на $2 b$ , а модуль чётность не меняет. Значит, замена пары $(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 клетки ровно по одному разу и вернуться в исходную угловую клетку? (Подсказка: раскрась доску и подумай, какой инвариант связан с ходом коня. Ответ «да» надо подтвердить примером маршрута, «нет» — инвариантом.)