Как решать задания 19, 20, 21 ЕГЭ (теория игр, выигрышная стратегия)?

Задания 19–21 — игра двух игроков (камни в куче/кучах, ходы по правилам: добавить, умножить). Нужно определить, кто и за сколько ходов выигрывает.

Понять две вещи:

• Выигрышная позиция — из неё ИГРОК, ЧЕЙ ХОД, может победить при правильной игре.
• Проигрышная (выигрышна для соперника) — любой ход ведёт в выигрышную для другого.

Универсальный способ — рекурсия с мемоизацией. Описываешь правила ходов и финал, а функция сама ищет, кто побеждает:

from functools import lru_cache

MOVES = lambda s: [s+1, s+2, s*2]   # ходы из условия
WIN = lambda s: s >= 35             # условие конца игры

@lru_cache(None)
def win(s):              # может ли победить тот, чей ход
    if WIN(s):
        return False     # игра кончилась — текущий уже не ходит
    return any(not win(ns) for ns in MOVES(s))

Дальше:

• 19 (выигрыш первого за 1 ход): среди ходов первого есть сразу финал.
• 20/21 — формализуй «выигрыш не позже 2-го хода» через глубину/чётность. Удобно завести функцию, возвращающую за сколько ходов выигрыш.

Частые ошибки:

• путать «выигрывает Петя/Ваня» (первый/второй игрок) и чей сейчас ход;
• неверно задать условие окончания (>= S камней) и набор ходов;
• забыть мемоизацию — на больших числах долго.

Главное — точно перенести правила ходов и финал. Логику «кто победит» Python выведет сам.