Инвариант и полуинвариант
Поиск сохраняющейся величины (инварианта) в задаче на процесс
Содержание 10 разделов
1. Метод инварианта: что это и зачем
Инвариант — это величина или свойство, которое не меняется при разрешённых операциях.
Зачем это нужно: чтобы доказать, что некоторое состояние недостижимо. Если в начальном состоянии инвариант имеет одно значение, а в конечном — другое, то переход невозможен.
Простой пример из жизни: представьте, что у вас есть 10 монет. Вы можете менять их на купюры, но общая сумма денег остаётся той же. Сумма — это инвариант. Если кто-то утверждает, что после обменов у вас стало больше денег, вы можете сказать: «Нет, сумма не меняется, значит, это невозможно».
Инвариант — это «якорь», который не даёт системе уйти в невозможное состояние. Найди его — и задача решена.
2. Алгоритм поиска инварианта
- Понять операции. Что разрешено делать? Какие действия выполняются над объектами?
- Найти величину, которая не меняется. Это может быть сумма, разность, остаток от деления, чётность, цвет клеток.
- Вычислить её в начальном состоянии.
- Вычислить её в предполагаемом конечном состоянии.
- Сравнить. Если значения разные — переход невозможен.
3. Самые частые инварианты в ЕГЭ
Инвариант 1: Чётность суммы
Утверждение: при замене двух чисел их суммой или разностью чётность общей суммы сохраняется.
Почему: если $a$ и $b$ заменить на $a+b$, то новая сумма изменится так: $S_{\text{нов}} = S_{\text{стар}} - a - b + (a+b) = S_{\text{стар}}$. Сумма вообще не меняется (не только чётность). Если заменить на $a-b$: $S_{\text{нов}} = S_{\text{стар}} - a - b + (a-b) = S_{\text{стар}} - 2b$. Разность $2b$ всегда чётна, значит чётность суммы сохраняется.
На доске написаны числа 1, 2, 3, 4. Разрешается стереть два числа и написать их сумму. Может ли на доске остаться нечётное число?
- Начальная сумма: $1+2+3+4=10$ (чётная).
- При замене двух чисел их суммой общая сумма не меняется.
- Значит, сумма всегда остаётся чётной.
- Нечётное число — это сумма из одного числа. Если на доске осталось одно нечётное число, то сумма всех чисел (равная этому числу) была бы нечётной.
- Противоречие: сумма должна быть чётной, а она нечётная.
Ответ: нет, не может.
Инвариант 2: Остаток от деления
Утверждение: если при операции к числу прибавляется число, кратное $k$, то остаток от деления на $k$ сохраняется.
Почему: если $a$ заменяется на $a + k \cdot t$, то $a$ и $a + k \cdot t$ дают одинаковый остаток при делении на $k$.
В трёх коробках: 64, 77 и 0 камней. За ход берут по одному камню из любых двух коробок и кладут в третью.
Рассмотрим разность между количеством камней во второй и первой коробках.
- Изначально: $77 - 64 = 13$.
- После операции разность меняется на $0$, $+3$ или $-3$.
- Значит, остаток от деления разности на $3$ сохраняется.
- $13 \equiv 1 \pmod 3$.
- Если в третьей коробке 141 камень, то в первой и второй по 0. Разность: $0$.
- $0 \equiv 0 \pmod 3$, а должно быть $1$ → противоречие.
Ответ: нет, не может.
Инвариант 3: Шахматная раскраска
Утверждение: при шахматной раскраске клетки $(i,j)$ имеют цвет, зависящий от чётности $i+j$. Если $i+j$ чётно — клетка одного цвета, если нечётно — другого.
Почему: при переходе на соседнюю клетку (вверх, вниз, влево, вправо) $i+j$ меняется на $1$, значит, цвет меняется на противоположный.
Доска $8\times8$ без двух противоположных угловых клеток. Можно ли замостить домино?
- В шахматной раскраске на доске $8\times8$ по 32 клетки каждого цвета.
- Противоположные угловые клетки — одного цвета (например, белого).
- После удаления двух белых клеток остаётся: белых — 30, чёрных — 32.
- Каждая доминошка покрывает 1 белую и 1 чёрную клетку.
- Для замощения нужно поровну клеток каждого цвета — а их не поровну.
Ответ: нет, нельзя.
4. Реальные примеры из ЕГЭ
Задача 1 (хамелеоны)
На острове живут 13 серых, 15 бурых и 17 малиновых хамелеонов. При встрече двух хамелеонов разного цвета они оба меняют свой цвет на третий. Может ли случиться, что через некоторое время все хамелеоны станут одного цвета?
Решение (инвариант).
- Рассмотрим разность между количеством бурых и серых хамелеонов: $B - S$.
- Изначально: $15 - 13 = 2$.
- Как меняется эта разность при операциях?
- Встретились серый и бурый → оба становятся малиновыми. $B$ уменьшается на 1, $S$ уменьшается на 1 → разность не меняется.
- Встретились серый и малиновый → оба становятся бурыми. $S$ уменьшается на 1, $B$ увеличивается на 2 → разность увеличивается на $3$.
- Встретились бурый и малиновый → оба становятся серыми. $B$ уменьшается на 1, $S$ увеличивается на 2 → разность уменьшается на $3$.
- Значит, остаток от деления разности $B-S$ на $3$ сохраняется.
- Изначально $B-S = 2 \equiv 2 \pmod 3$.
- Если все хамелеоны одного цвета, то либо $B-S = 45$ (все бурые), либо $B-S = -45$ (все серые), либо $B-S = 0$ (все малиновые).
- $45 \equiv 0 \pmod 3$, $-45 \equiv 0 \pmod 3$, $0 \equiv 0 \pmod 3$.
- Ни одно из этих значений не сравнимо с $2$ по модулю $3$.
Ответ: нет, не может.
Задача 2 (камни, ЕГЭ-2022)
В трёх коробках: 64, 77 и 0 камней. За ход берут по одному камню из любых двух коробок и кладут в третью.
а) Может ли быть (64;59;18)?
б) Может ли в третьей быть 141 камень?
в) Если в первой 1 камень, какое максимальное число камней может быть в третьей?
Решение.
- Пункт а) Да. Покажем последовательность шагов: $(64;77;0) \to (63;76;2) \to (62;75;4) \to (64;74;3) \to (63;73;5) \to (62;72;7) \to (61;74;6) \to \dots$ → в итоге можно получить $(64;59;18)$.
- Пункт б) Нет. Рассмотрим разность между второй и первой коробками: $77 - 64 = 13$. При операции разность меняется на $0$, $+3$ или $-3$. Значит, остаток от деления на $3$ сохраняется: $13 \equiv 1 \pmod 3$. Если в третьей 141 камень, то в первой и второй по 0, разность $0 \equiv 0 \pmod 3$ — противоречие.
- Пункт в) Если в первой коробке 1 камень, то разность $b-1$ должна иметь остаток $1 \pmod 3$ (так как $13 \equiv 1 \pmod 3$). Значит, $b-1 \equiv 1 \pmod 3$ → $b \equiv 2 \pmod 3$. Минимальное $b \ge 0$ с таким остатком — это $b=2$. Тогда в третьей коробке: $141 - 1 - 2 = 138$.
Ответ: а) да; б) нет; в) 138.
5. Типичные ошибки
| Ошибка | Как правильно |
| Выбрать неинвариантную величину | Проверьте, действительно ли она не меняется при всех операциях. |
| Забыть про остатки | Часто инвариант — это остаток от деления на $k$. |
| Не учесть все операции | Проверьте инвариантность для всех разрешённых операций. |
| Путать инвариант и полуинвариант | Инвариант не меняется, полуинвариант только возрастает или убывает. |
| Не проверить достижимость | Если вы нашли оценку, обязательно покажите пример, где она достигается. |
Подпишись — и вся теория откроется
72 темы ЕГЭ и 72 темы ОГЭ с разборами примеров. Доступ откроется сразу и сохранится в этом браузере.