Рассмотрим игру с кучей из палочек. Алиса и Боб ходят по очереди, при этом Алиса ходит первой. На каждом ходу игрок должен убрать из кучи , или палочки. Игрок, который убирает последнюю палочку, выигрывает.
Мы представляем состояние игры как , где — количество оставшихся палочек.
Согласно условию задачи:
Решите эти внешние задачи (например, из Codeforces) чтобы закрепить материал урока:
Выигрышное состояние — это состояние, из которого текущий игрок может гарантировать победу, если оба игрока играют оптимально.
Проигрышное состояние — это состояние, из которого текущий игрок проиграет, если соперник также играет оптимально.
Таким образом, каждое состояние игры можно классифицировать как выигрышное или проигрышное.
Рассмотрим игру выше:
Это даёт основное правило:
Используя эту идею, мы можем классифицировать все состояния одно за другим, начиная с состояний, где ходы невозможны.
Для игры выше состояния от до классифицируются следующим образом:
| Состояния | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Результат | L | W | W | W | L | W | W | W | L | W | W | W | L |
Здесь W означает выигрышное состояние, а L означает проигрышное состояние.
Теперь рассмотрим другую игру с палочками.
В состоянии игрок может убрать любое количество палочек такое, что:
Например:
Мы можем представить игру в виде графа:
В этой игре процесс всегда заканчивается в состоянии , потому что там ход невозможен. Поэтому состояние — проигрышное состояние.
После классификации всех состояний мы получаем следующую картину, где проигрышные состояния отмечены красным, а выигрышные — зелёным:
N = 7 -> Начальное состояние (n = 7)
Алиса убирает 3 палочки -> Новое состояние (n = 4)
Боб убирает 2 палочки -> Новое состояние (n = 2)
Алиса убирает 2 палочки -> Новое состояние (n = 0)