Задание 21 ЕГЭ по информатике: дерево игры и стратегия Вани

Задание 21 ЕГЭ по информатике проверяет умение построить дерево игры и найти выигрышную стратегию: нужно найти S, при котором Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может обеспечить себе выигрыш первым ходом. Решение опирается на позиции, найденные в заданиях 19 и 20.

Как решать

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

Используйте группы позиций. A — выигрыш одним ходом. B — проигрыш того, кто ходит: любой ход ведёт в A. C — позиции, из которых можно одним ходом попасть в B, то есть выигрыш вторым ходом. Исходная позиция подходит для задания 21, если любой ход Пети ведёт в A или C и хотя бы один ход ведёт в C.

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

В программе условие записывается как game(s, 4) and not game(s, 2): при m = 4 Ваня выигрывает не позже своего второго хода, а m = 2 соответствует выигрышу первым ходом.

Примеры с решением

Пример 1

У Пети и Вани есть куча из S камней, 1 ≤ S ≤ 39. Игроки ходят по очереди, первый ход за Петей. За ход разрешено добавить в кучу один или три камня либо удвоить количество камней. Игра заканчивается в момент, когда в куче становится не менее 40 камней, и побеждает тот, кто сделал последний ход.

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

Проверка ответа на Python

from functools import lru_cache


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


@lru_cache(None)
def game(s, m):
    if s >= 40:
        return m % 2 == 0
    if m == 0:
        return False
    h = [game(x, m - 1) for x in moves(s)]
    return any(h) if (m - 1) % 2 == 0 else all(h)


# Ваня выигрывает первым или вторым ходом (m = 4), но не гарантированно первым (m = 2).
print(min(s for s in range(1, 40) if game(s, 4) and not game(s, 2)))

Ответ: 15

Одним ходом выигрывают позиции от 20 до 39. Позиция 19 проигрышна для того, кто ходит: 20, 22 и 38 лежат в этом промежутке. Из 16 и 18 можно попасть в 19, это выигрыш вторым ходом. При S = 15 ходы Пети ведут в 16, 18 или 30. Из 30 Ваня выигрывает сразу, из 16 и 18 он ходит в 19, и после любого хода Пети выигрывает вторым ходом. Выигрыш первым ходом Ваня обеспечить не может: из 16 и 18 до 40 одним ходом не дойти. Для S от 1 до 14 условие не выполняется.

Пример 2

Две кучи камней: в первой 5 камней, во второй S камней, 1 ≤ S ≤ 58. Петя и Ваня ходят по очереди, первым ходит Петя. За ход игрок добавляет три камня в одну из куч или удваивает одну из куч. Когда в двух кучах суммарно становится 64 камня или больше, игра заканчивается; побеждает игрок, сделавший последний ход.

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

Проверка ответа на Python

from functools import lru_cache


def moves(p):
    a, b = p
    return [(a + 3, b), (a, b + 3), (a * 2, b), (a, b * 2)]


@lru_cache(None)
def game(p, m):
    if sum(p) >= 64:
        return m % 2 == 0
    if m == 0:
        return False
    h = [game(x, m - 1) for x in moves(p)]
    return any(h) if (m - 1) % 2 == 0 else all(h)


print(min(s for s in range(1, 59) if game((5, s), 4) and not game((5, s), 2)))

Ответ: 23

При S = 23 Петя может получить (8, 23), (5, 26), (10, 23) или (5, 46). Из (5, 46) Ваня выигрывает сразу, удвоив вторую кучу. В остальных случаях Ваня переводит игру в позицию, из которой любой ход Пети даёт ему выигрыш: (8, 23) → (16, 23), (5, 26) → (5, 29), (10, 23) → (10, 26). Выигрыш первым ходом Ваня обеспечить не может: из (5, 26) одним ходом не набрать 64 камня, наибольшая сумма 5 + 52 = 57.

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

Потренироваться на тренажёре

Частые вопросы

Как проверить ответ к заданию 21 без программы?

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

Почему в ответе одно число, хотя подходящих S несколько?

Условие спрашивает наименьшее значение, в других вариантах — наибольшее. Остальные подходящие S в ответ не записывают.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 20 и задание 22.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.