ЕГЭ по информатике 2026, задание 21: дерево игры

Задание 21 — повышенный уровень, 1 балл, та же партия. Часто нужно значение S, при котором у Вани есть выигрышная стратегия, а у Пети нет стратегии выиграть раньше, чем за два своих хода, и спрашивают конкретное S или два значения.

Если ответ не виден из решения №20, ФИПИ рекомендует дерево: полное или неполное, схема или таблица на черновике. Неполное дерево допустимо, только если вы осознанно отсекаете ветки, которые не меняют вывод. «Не смотрел вторую кучу» — не отсечение, а ошибка.

Конспект

Вопрос №21 обычно на ход длиннее, чем №20. Ваня выигрывает своим вторым ходом, когда:

• Петя не может закончить игру раньше;
• как бы Петя ни ходил первым ходом, Ваня может ответить так, чтобы дальше у Пети не было спасения, и Ваня завершит игру на своём втором ходу.

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

Неполное дерево: сначала выпишите ходы Пети из стартового S. Если хотя бы на один ход Пети у Вани нет нужного ответа, S не подходит, дальше эту ветку не рисуйте. Если все первые ходы Пети разобраны и на каждый есть ответ, позиция годится.

Не переносите S из №20 в №21 без чтения вопроса. Иногда просят те же числа, иногда следующее по величине, иногда позицию, где выигрывает уже второй игрок.

Шаблон на Python

Здесь рекурсия с глубиной хода. turns=4 — четыре полухода, то есть второй ход Вани. Подстройте функцию под формулировку: кто выигрывает и не раньше какого хода.

GOAL = 129
memo = {}

def moves(s):
    return [s + 1, s * 2]

def wins(s, turns_left):
    key = (s, turns_left)
    if key in memo:
        return memo[key]
    if s >= GOAL or turns_left == 0:
        memo[key] = False
        return False
    # текущий игрок выигрывает, если может сразу закончить
    # или оставить сопернику позицию, где тот не выигрывает
    result = False
    for m in moves(s):
        if m >= GOAL or not wins(m, turns_left - 1):
            result = True
            break
    memo[key] = result
    return result

# позиции, где первый не выигрывает за 1 и за 3 полухода,
# но второй выигрывает: проверяйте по точной формулировке варианта
for s in range(1, GOAL):
    if any(m >= GOAL for m in moves(s)):
        continue
    print(s, wins(s, 1), wins(s, 3))

Готовый print не копируйте в бланк. Сначала сопоставьте «победа за 3 полухода» с текстом: чей это ход и исключены ли более ранние победы. Шаблон считает факт победы не позднее заданной глубины. Для №21 почти всегда нужно ещё отсечь более быстрые победы.

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

• Дерево оборвано на ходе, где соперник ещё мог спастись.
• Победа за 2 хода второго игрока смешана с победой за 2 хода первого.
• Из №20 переписаны числа без проверки, что вопрос другой.
• В двух кучах ход применён к обеим сразу.