Дерево игры

Простыми словами

Задание 21 — самое длинное из игровой тройки. Нужно рассмотреть все ходы Пети и для каждого — лучший ответ Вани, на две пары ходов вперёд. Ветвей немного (обычно 4–8), и ошибаются не от сложности, а от пропущенной ветки.

Пример тот же: ходы +1 и ×2, порог 29. Из заданий 19–20: W1 — $S$ от 15 до 28, L1 — 14, W2 — 7 и 13.

Что значит формулировка

«У Вани есть стратегия, позволяющая выиграть первым или вторым ходом при любой игре Пети, но нет стратегии, которая позволит ему гарантированно выиграть первым ходом». Это два условия одновременно:

Дерево игры для S = 12

1. Петя: 12 → 24. Ваня удваивает: 48 ≥ 29 — победа первым ходом.
2. Петя: 12 → 13. Ваня не может выиграть сразу ($26<29$), поэтому ходит +1 → 14 (L1).
3. Из 14 Петя может сделать 15 или 28 — обе позиции W1, Ваня выигрывает вторым ходом.
4. Условие 1 выполнено (выигрыш при любом ходе), условие 2 тоже (после 13 сразу не выиграть). Ответ: 12.

Таблица разбора и программа

Удобная схема — таблица из четырёх столбцов: позиция, ход Пети, ответ Вани, итог. Кандидатов проверяйте снизу вверх; если подходящих несколько, а спрашивают наименьшее — берите первое.

N = 29
def moves(s): return [s + 1, s * 2]
def win(s, k):          # игрок, который ходит из s, выигрывает не позднее k-го хода
    if k == 0: return False
    return any(m >= N or lose(m, k - 1) for m in moves(s))
def lose(s, k):         # каждый ход из s ведёт в позицию, выигрышную для соперника за k
    return all(m < N and win(m, k) for m in moves(s))

print([s for s in range(1, N) if lose(s, 2) and not lose(s, 1)])   # [12]