ЕГЭ Задание 19, 20, 21

В этой статье будет разобраны задания 19, 20, 21.

Рассмотрим задачи последних лет из демоверсий ЕГЭ по информатике. Эти задания относятся к теории игр, они взаимосвязаны по условию и решаются подряд.

Задание 19 относится к базовому уровню сложности. Время выполнения задания 19 ≈ 6 минут.

Задание 20 относится к повышенному уровню сложности. Время выполнения задания 20 ≈ 8 минут.

Задание 21 относится к высокому уровню сложности. Время выполнения задания 21 ≈ 11 минут.

Задача 1 (Демоверсия ЕГЭ 2023-24)

Задание 19

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

Решение:

Решение на Python

В цикле перебираем все значения стартовой позиции(кол-во камней в куче). И до этого важно прописать функцию, которая вызывая сама себя(рекурсия) по условию задачи найдёт решение.

def F19(x, p):  # x - кол-во камней в куче, p - кто ходит 1 - Петя, 2 - Ваня, 3 - Петя и т.д.
    if x >= 129 and p == 3:  # Если ход 3(Пети), и кол-во камней стало 129 или более - значит Ваня победил 2 ходом
        return True
    if x <= 129 and p == 3:
        return False
    if x >= 129:
        return False

    if p % 2 != 0:  # Номер хода нечётный значит ходит Петя
        return F19(x + 1, p + 1) and F19(x * 2, p + 1)  # Чтобы Ваня выиграл необходимо проверять оба условия хода Пети
    else:
        return F19(x + 1, p + 1) or F19(x * 2, p + 1)  # Иначе ход Вани


for s in range(1, 129):
    if F19(s, 1):
        print('Задача 19: ', s)

Ответ: 64

Задание 20

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

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

Найденные значения запишите в ответе в порядке возрастания.

Решение:

Решение на Python

Решается задача аналогичным способом задачи 19. Меняется только условие выхода из рекурсии(p == 4) т.к. теперь рассматриваем победу Пети. И условие входа в рекурсию меняем p % 2 == 0: т.е. опять же, чтобы выиграл Петя, необходимо проверить как бы не ходил Ваня(его номера ходов 2, 4, 6 и т.д. т.е. чётные).

def F20(x, p):
    if x >= 129 and p == 4:
        return True
    if x <= 129 and p == 4:
        return False
    if x >= 129:
        return False

    if p % 2 == 0:
        return F20(x + 1, p + 1) and F20(x * 2, p + 1)
    else:
        return F20(x + 1, p + 1) or F20(x * 2, p + 1)


for s in range(1, 129):
    if F20(s, 1):
        print('Задача 20: ', s)

Ответ: 32 | 63

Задание 21

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Если найдено несколько значений S, в ответе запишите минимальное из них.

Решение:

Решение на Python

Меняется опять же условие входа в рекурсию от Вани как в задании 19. p % 2 != 0 и проверяем выход из функции победил Ваня своим 1 или 2 ходом. При этом результат(ы) из задания 19, где Ваня побеждает гарантированно первым ходом нужно исключить из ответов. И выбрать один единственно правильный ответ.

def F21(x, p):
    if x >= 129 and (p == 3 or p == 5):
        return True
    if x <= 129 and p == 5:
        return False
    if x >= 129:
        return False

    if p % 2 != 0:
        return F21(x + 1, p + 1) and F21(x * 2, p + 1)
    else:
        return F21(x + 1, p + 1) or F21(x * 2, p + 1)


for s in range(1, 129):
    if F21(s, 1):
        print('Задача 21: ', s)  # То что вернула в 19 задании функция F19 нужно исключить из ответов

Ответ: 62

Задача 2 (Демоверсия ЕГЭ 2025)

Задание 19

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из кучи два камня или убрать из кучи пять камней или уменьшить количество камней в куче в три раза (количество камней, полученное при делении, округляется до меньшего). Например, из кучи в 20 камней за один ход можно получить кучу из 18, 15 или 6 камней. Игра завершается, когда количество камней в куче становится не более 19. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней. В начальный момент в куче было S камней, S ≥ 20. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Решение:

Решение на Python

В цикле перебираем все значения стартовой позиции(кол-во камней в куче). И до этого важно прописать функцию, которая вызывая сама себя(рекурсия) по условию задачи найдёт решение.

def F19(x, p):  # x - кол-во камней в куче, p - кто ходит 1 - Петя, 2 - Ваня, 3 - Петя и т.д.
    if x <= 19 and p == 3:  # Если ход 3(Пети), и кол-во камней стало 19 или менее - значит Ваня победил вторым ходом
        return True
    if x > 19 and p == 3:
        return False
    if x <= 19:
        return False
    if p % 2 != 0:  # Номер хода нечётный значит ходит Петя
        # Чтобы Ваня гарантированно выиграл — необходимо проверять все три условия хода Пети
        return F19(x - 2, p + 1) and F19(x - 5, p + 1) and F19(x // 3, p + 1)
    else:
        return F19(x - 2, p + 1) or F19(x - 5, p + 1) or F19(x // 3, p + 1)  # Иначе ход Вани


for s in range(20, 80):
    if F19(s, 1):
        print('Ответ на задачу 19: ', s)  # Выбираем в консоли минимальное значение

Ответ: 60

Задание 20

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

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

Найденные значения запишите в ответе в порядке возрастания.

Решение:

Решение на Python

Решается задача аналогичным способом задачи 19. Меняется только условие выхода из рекурсии(p == 4) т.к. теперь рассматриваем победу Пети. И условие входа в рекурсию меняем p % 2 == 0: т.е. опять же, чтобы выиграл Петя, необходимо проверить как бы не ходил Ваня(его номера ходов 2, 4, 6 и т.д. т.е. чётные).

def F20(x, p):  # x - кол-во камней в куче, p - кто ходит 1 - Петя, 2 - Ваня, 3 - Петя и т.д.
    if x <= 19 and p == 4:  # Если ход 4(Вани), и кол-во камней стало 19 или менее - значит Петя победил вторым ходом
        return True
    if x > 19 and p == 4:
        return False
    if x <= 19:
        return False
    if p % 2 == 0:  # Номер хода чётный значит ходит Ваня
        # Чтобы Петя гарантированно выиграл — необходимо проверять все три условия хода Вани
        return F20(x - 2, p + 1) and F20(x - 5, p + 1) and F20(x // 3, p + 1)
    else:
        return F20(x - 2, p + 1) or F20(x - 5, p + 1) or F20(x // 3, p + 1)  # Иначе ход Пети


for s in range(20, 80):
    if F20(s, 1):
        print('Ответ на задачу 20: ', s)

В консоли выбираем два наименьших числа из ответов и запишем в ответ на задачу.

Ответ: 62 | 63

Задание 21

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Решение:

Решение на Python

Меняется опять же условие входа в рекурсию от Вани как в задании 19. p % 2 != 0 и проверяем выход из функции победил Ваня своим 1 или 2 ходом. При этом результат(ы) из задания 19, где Ваня побеждает гарантированно первым ходом нужно исключить из ответов. И выбрать один единственно правильный ответ(минимальное значение после ответов из 19 задания).

def F21(x, p):  # x - кол-во камней в куче, p - кто ходит 1 - Петя, 2 - Ваня, 3 - Петя и т.д.
    # # Если ход 3 или 5(Пети), и кол-во камней стало 19 или менее
    if x <= 19 and (p == 3 or p == 5):
        return True  # Значит Ваня победил вторым ходом
    if x > 19 and p == 5:
        return False
    if x <= 19:
        return False
    if p % 2 != 0:  # Номер хода нечётный значит ходит Петя
        # Чтобы Ваня гарантированно выиграл — необходимо проверять все три условия хода Пети
        return F21(x - 2, p + 1) and F21(x - 5, p + 1) and F21(x // 3, p + 1)
    else:
        return F21(x - 2, p + 1) or F21(x - 5, p + 1) or F21(x // 3, p + 1)  # Иначе ход Вани


for s in range(20, 80):
    if F21(s, 1):
        print('Ответ на задачу 21: ', s)  # То что вернула в 19 задании функция F19 нужно исключить из ответов

Числа 60, 61 - не являются ответом, т.к. они получились и в задании 19.

Ответ: 64

Задача 3 (Демоверсия 2026)

Задание 19

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может: убрать из кучи три камня или убрать из кучи пять камней или уменьшить количество камней в куче в четыре раза (количество камней, полученное при делении, округляется до меньшего). Например, из кучи в 20 камней за один ход можно получить кучу из 17, 15 или 5 камней. Игра завершается, когда количество камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 30 или меньше камней. В начальный момент в куче было S камней, S ≥ 31. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Решение:

Решение на Python

В цикле перебираем все значения стартовой позиции(кол-во камней в куче). И до этого важно прописать функцию, которая вызывая сама себя(рекурсия) по условию задачи найдёт решение.

def F19(x, p):  # x - кол-во камней в куче, p - кто ходит 1 - Петя, 2 - Ваня, 3 - Петя и т.д.
    if x <= 30 and p == 3:  # Если ход 3(Пети), и кол-во камней стало 30 или менее - значит Ваня победил вторым ходом
        return True
    if x > 30 and p == 3:
        return False
    if x <= 30:
        return False
    if p % 2 != 0:  # Номер хода нечётный значит ходит Петя
        # Чтобы Ваня гарантированно выиграл — необходимо проверять все три условия хода Пети
        return F19(x - 3, p + 1) and F19(x - 5, p + 1) and F19(x // 4, p + 1)
    else:
        return F19(x - 3, p + 1) or F19(x - 5, p + 1) or F19(x // 4, p + 1)  # Иначе ход Вани


for s in range(31, 200):
    if F19(s, 1):
        print('Ответ на задачу 19: ', s)

Ответ: 124

Задание 20

Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

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

Найденные значения запишите в ответе в порядке возрастания.

Решение:

Решение на Python

Решается задача аналогичным способом задачи 19. Меняется только условие выхода из рекурсии(p == 4) т.к. теперь рассматриваем победу Пети. И условие входа в рекурсию меняем p % 2 == 0: т.е. опять же, чтобы выиграл Петя, необходимо проверить как бы не ходил Ваня(его номера ходов 2, 4, 6 и т.д. т.е. чётные).

def F20(x, p):  # x - кол-во камней в куче, p - кто ходит 1 - Петя, 2 - Ваня, 3 - Петя и т.д.
    if x <= 30 and p == 4:  # Если ход 4(Вани), и кол-во камней стало 30 или менее - значит Петя победил вторым ходом
        return True
    if x > 30 and p == 4:
        return False
    if x <= 30:
        return False
    if p % 2 == 0:  # Номер хода чётный значит ходит Ваня
        # Чтобы Петя гарантированно выйграл — необходимо проверять все три условия хода Вани
        return F20(x - 3, p + 1) and F20(x - 5, p + 1) and F20(x // 4, p + 1)
    else:
        return F20(x - 3, p + 1) or F20(x - 5, p + 1) or F20(x // 4, p + 1)  # Иначе ход Пети


for s in range(31, 200):
    if F20(s, 1):
        print('Ответ на задачу 20: ', s)

В консоли выбираем два наименьших числа из ответов и запишем в ответ на задачу.

Ответ: 127 | 128

Задание 21

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Решение:

Решение на Python

Меняется опять же условие входа в рекурсию от Вани как в задании 19. p % 2 != 0 и проверяем выход из функции победил Ваня своим 1 или 2 ходом. При этом результат(ы) из задания 19, где Ваня побеждает гарантированно первым ходом нужно исключить из ответов. И выбрать один единственно правильный ответ(минимальное значение после ответов из 19 задания).

def F21(x, p):  # x - кол-во камней в куче, p - кто ходит 1 - Петя, 2 - Ваня, 3 - Петя и т.д.
    if x <= 30 and (p == 3 or p == 5):  # Если ход 3 или 5, значит ходит Петя
        return True  # Значит Ваня победил вторым ходом
    if x > 30 and p == 5:
        return False
    if x <= 30:
        return False
    if p % 2 != 0:  # Номер хода нечётный значит ходит Петя
        # Чтобы Ваня гарантированно выиграл — необходимо проверять все три условия хода Пети
        return F21(x - 3, p + 1) and F21(x - 5, p + 1) and F21(x // 4, p + 1)
    else:
        return F21(x - 3, p + 1) or F21(x - 5, p + 1) or F21(x // 4, p + 1)  # Иначе ход Вани


for s in range(31, 200):
    if F21(s, 1):
        print('Ответ на задачу 21: ', s) # То что вернула в 19 задании функция F19 нужно исключить из ответов

Числа 124, 125, 126 - не являются ответом, т.к. они получились и в задании 19.

Ответ: 132

Попробуйте сами запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.