Выигрышные и проигрышные позиции (задание 19)

Зачем это в ЕГЭ.
Задание 19 проверяет умение анализировать выигрышные и проигрышные позиции в играх с двумя участниками. Это одно из самых сложных заданий, оцениваемое в 1 первичный балл. Встречается почти в каждом варианте ФИПИ.

Главная идея.
Суть задачи — определить, кто выиграет при оптимальной игре: первый или второй игрок. Ключ к решению — построение дерева возможных ходов и анализ позиций, начиная с конца игры.

Алгоритм (чеклист).
1. Определите начальную позицию и правила игры.
2. Постройте дерево возможных ходов, начиная с конечных позиций.
3. Для каждой позиции определите, является ли она выигрышной или проигрышной.
4. Проверьте, можно ли выиграть за один ход из начальной позиции.
5. Сделайте вывод о победителе при оптимальной игре.

**Опоры (кратко).
- Позиция выигрышная, если из неё есть хотя бы один ход в проигрышную позицию.
- Позиция проигрышная, если все возможные ходы ведут в выигрышные позиции.
- Формула для анализа: если $S$ — количество камней, то $S \mod (k+1) = 0$ — проигрышная позиция, где $k$ — максимальное количество камней, которое можно взять за ход.

Пример 1 (подтип: анализ позиций)
Шаг 1. Начальная позиция: 10 камней. За ход можно взять 1 или 2 камня.
Шаг 2. Построим дерево ходов от конечных позиций:
- Позиция 0: проигрышная.
- Позиция 1: выигрышная (можно взять последний камень).
- Позиция 2: выигрышная (можно взять 2 камня).
Шаг 3. Анализируем позиции:
- Позиция 3: проигрышная (все ходы ведут в выигрышные позиции).
- Позиция 4: выигрышная (можно взять 1 камень и перевести в позицию 3).
Шаг 4. Начальная позиция 10: выигрышная (можно взять 1 камень и перевести в позицию 9).
Шаг 5. Вывод: первый игрок выигрывает при оптимальной игре.

Пример 2 (подтип: применение формулы)
Шаг 1. Начальная позиция: 15 камней. За ход можно взять от 1 до 3 камней.
Шаг 2. Применим формулу: $S \mod (k+1) = 15 \mod 4 = 3$.
Шаг 3. Поскольку результат не равен 0, позиция выигрышная.
Шаг 4. Первый игрок может взять 3 камня и перевести в позицию 12 (проигрышную).
Шаг 5. Вывод: первый игрок выигрывает при оптимальной игре.

Типичные ошибки.
1. Неправильный анализ конечных позиций. Неверное определение проигрышных и выигрышных позиций.
2. Игнорирование оптимальной стратегии. Упущение того, что оба игрока играют оптимально.
3. Ошибка в применении формулы. Неправильное использование формулы для анализа позиций.
4. Неполное дерево ходов. Пропуск возможных ходов в дереве.
5. Неправильный вывод. Ошибка в определении победителя при оптимальной игре.

Дальше.
Переходите к задачам на анализ игр с более сложными правилами и большим количеством ходов.