Тема 64 из 72 · Теория чисел

Теория игр. Раскраска. Графы

Выигрышные стратегии, раскраска клеток, графы в олимпиадных задачах

ТГ-каналПодписывайся · там же запись на вводный урок t.me/algo_math ↗

1. Математические игры: что это такое

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

Основные понятия:

Позиция P (проигрышная): любой ход из неё ведёт в выигрышную позицию.
Позиция W (выигрышная): есть хотя бы один ход в проигрышную позицию.

Важно

Если вы находитесь в W-позиции, вы можете выиграть (если правильно сходите). Если вы в P-позиции, вы проиграете при правильной игре соперника.

2. Базовый алгоритм анализа игр

Определить начальную позицию.
Разобрать малые позиции. Найти P и W для небольшого количества ходов.
Найти закономерность. Часто P-позиции образуют арифметическую прогрессию.
Доказать закономерность. Показать, что из P-позиции любой ход ведёт в W, а из W есть ход в P.

3. Классический пример: игра с камнями

Пример

В кучке $n$ камней. За ход можно взять 1 или 2 камня. Выигрывает тот, кто берёт последний камень. Кто выигрывает при $n=10$?

Решение.

Анализируем малые позиции:

$n=0$: ходов нет → P-позиция (проигрышная).
$n=1$: можно взять 1 и перейти в $n=0$ (P) → W-позиция.
$n=2$: можно взять 2 и перейти в $n=0$ (P) → W-позиция.
$n=3$: можно взять 1 → $n=2$ (W) или 2 → $n=1$ (W). Все ходы ведут в W → P-позиция.
$n=4$: можно взять 1 → $n=3$ (P) → W-позиция.
$n=5$: можно взять 2 → $n=3$ (P) → W-позиция.
$n=6$: все ходы ведут в W → P-позиция.

Закономерность: P-позиции — это $n$, кратные 3: $0, 3, 6, 9, 12, \ldots$
$n=10$: $10$ не кратно 3 → W-позиция.
Стратегия: брать $3-k$, где $k$ — сколько взял соперник, чтобы оставить количество камней, кратное 3.

Ответ: Первый игрок выигрывает (при $n=10$).

4. Игры на двух кучах (симметричная стратегия)

Пример (ЕГЭ-подобный)

В двух кучах лежит по 20 конфет. За ход можно взять любое количество конфет, но только из одной кучи. Выигрывает тот, кто берёт последнюю конфету. Кто выигрывает?

Решение.

Используем симметричную стратегию для второго игрока.
Второй игрок всегда берёт столько же конфет из другой кучи, сколько взял первый.
После хода второго игрока в кучках снова поровну.
Так как первый игрок не может взять конфеты из двух куче одновременно, второй всегда может ответить.
Второй игрок берёт последнюю конфету.

Ответ: Второй игрок выигрывает.

5. Реальный пример из ЕГЭ (задача №20)

Задача из ЕГЭ (про камни)

В кучке лежат 100 камней. Двое игроков по очереди берут из кучки 1, 2 или 5 камней. Выигрывает тот, кто берёт последний камень. Кто выигрывает при правильной игре?

Решение.

Анализируем малые позиции:

$n=0$: P
$n=1$: можно взять 1 → P → W
$n=2$: можно взять 2 → P → W
$n=3$: можно взять 1 → W, 2 → W, 5 нельзя → все ходы в W → P
$n=4$: можно взять 1 → P → W
$n=5$: можно взять 5 → P → W
$n=6$: можно взять 1 → W ($n=5$), 2 → W ($n=4$), 5 → W ($n=1$) → все ходы в W → P
$n=7$: можно взять 1 → P ($n=6$) → есть ход в P → W
$n=8$: можно взять 2 → P ($n=6$) → есть ход в P → W
$n=9$: можно взять 1 → W ($n=8$), 2 → W ($n=7$), 5 → W ($n=4$) → все ходы в W → P

Закономерность: P-позиции — это $n$, кратные $3$: $0, 3, 6, 9, \ldots$ (ход «5» при делении на 3 даёт тот же остаток, что и ход «2», поэтому структура остатков как в игре с ходами $\{1,2\}$ сохраняется).
$100 = 33\cdot3+1$, то есть $100 \not\equiv 0 \pmod 3$ → W-позиция.
Первый игрок выигрывает.

Ответ: Первый игрок.

6. Типичные ошибки

Ошибка	Как правильно
Не доказать закономерность	Обязательно покажите, что из P-позиции все ходы ведут в W, а из W есть ход в P.
Считать, что всегда выигрывает первый	При правильной игре выигрывает тот, кто может сделать ход в P-позицию.
Не проверить все возможные ходы	Из P-позиции все ходы должны вести в W.
Забыть про симметричную стратегию	В играх с двумя одинаковыми кучами часто работает симметрия.

← 63. Принцип крайнего. Принцип Дирихле 65. Марафон первой части №1–5 →