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

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

Что проверяет: Умение найти выигрышную стратегию игры. Игра та же, что в задании 19 того же варианта: меняется только вопрос.
Баллы: 1 первичный балл
Формат ответа: Два целых числа через пробел в порядке возрастания
Программа: задание решают без программы, ответ можно проверить на Python
Уровень сложности: повышенный
Время: около 7 минут по спецификации
Кодификатор: 2.15 — дискретные игры двух игроков с полной информацией; построение дерева перебора вариантов, описание стратегии игры в табличной форме; выигрышные и проигрышные позиции; выигрышные стратегии; требование 2.1 — умение использовать компьютерно-математические модели для анализа объектов и процессов

Как решать

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

Петя выигрывает вторым ходом, если может одним ходом перевести игру во вторую группу. Тогда Ваня вынужден сделать ход в позицию первой группы, и Петя заканчивает игру. Отдельно проверьте, что из исходной позиции Петя не выигрывает сразу: условие задания это исключает.

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

В программе это функция game(s, m) с m = 3: ходы Пети проверяются через any, ход Вани — через all. Условие «Петя не может выиграть за один ход» проверяется вызовом game(s, 1), который должен вернуть False.

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

Пример 1

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

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

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

from functools import lru_cache


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


@lru_cache(None)
def game(s, m):
    if s >= 60:
        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 = 3), но не может выиграть первым ходом (m = 1).
found = [s for s in range(1, 60) if game(s, 3) and not game(s, 1)]
print(*found[:2])

Ответ: 6 13

Одним ходом выигрывают позиции от 20 до 59: утроение даёт не меньше 60. Позиции 18 и 19 проигрышны для того, кто ходит: ходы +2, +5 и ×3 ведут в промежуток от 20 до 59, откуда соперник выигрывает. Петя выигрывает вторым ходом, если может попасть в 18 или 19: из 6 утроением, из 13 и 14 добавлением пяти камней, из 16 и 17 добавлением двух. Два наименьших значения — 6 и 13.

Пример 2

Петя и Ваня играют с двумя кучами камней: в первой 9 камней, во второй S камней, 1 ≤ S ≤ 60. Ходят по очереди, начинает Петя. За ход можно положить один камень в любую кучу или увеличить любую кучу вдвое. Игра останавливается, когда в двух кучах вместе становится не меньше 70 камней, и победителем считается автор последнего хода.

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

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

from functools import lru_cache


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


@lru_cache(None)
def game(p, m):
    if sum(p) >= 70:
        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)


found = [s for s in range(1, 61) if game((9, s), 3) and not game((9, s), 1)]
print(*found[:2])

Ответ: 15 29

Из позиции (9, S) игрок выигрывает одним ходом при S ≥ 31: 9 + 2 × 31 = 71. Позиция (9, 30) проигрышна для того, кто ходит: из неё нельзя набрать 70 камней (9 + 60 = 69), а после каждого хода — (10, 30), (9, 31), (18, 30) или (9, 60) — соперник выигрывает одним ходом. Петя попадает в (9, 30) из S = 15 удвоением второй кучи и из S = 29 добавлением камня во вторую кучу. Меньших подходящих S нет, ответ: 15 и 29.

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

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

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

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

Что значит «выигрывает независимо от того, как будет ходить Ваня»?

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

Как записать ответ из двух чисел?

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

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

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

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

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