ЕГЭ · краткий ответ

Задание 21 ЕГЭ по информатике — теория игр: выигрыш первым или вторым ходом

Что проверяет номер, типичные ошибки, пример с решением на Python и 10 заданий с ответами под спойлером.

40заданий в банке
с ответамикак в КИМ
1 кликзадание на доске

Что проверяет задание 21 ЕГЭ

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

КЕГЭ, задание 2140 заданий в банке ИнфДоски

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

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

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

Условие

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

Решение

Из S = 22 Петя может пойти в 23 или в 44. Из 44 Ваня выигрывает сразу (удвоение), из 23 Ваня ходит в 24 — проигрышную для Пети позицию — и выигрывает вторым ходом. Гарантированного выигрыша первым ходом нет. Ответ: 22.

from functools import lru_cache

@lru_cache(None)
def game(s):
    moves = [s + 1, s * 2]
    if any(t >= 50 for t in moves):
        return ('W', 1)
    res = [game(t) for t in moves]
    wins = [k + 1 for c, k in res if c == 'L']
    return ('W', min(wins)) if wins else ('L', max(k for c, k in res))

print(min(s for s in range(1, 50) if game(s) == ('L', 2)))
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 22

Задания из банка

В банке ИнфДоски 40 заданий этого номера. Ниже — 10 из них, ответ спрятан под спойлером. Кнопка «Открыть на доске» ставит задание на вашу ИнфДоску.

Задание 1 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ
16
Задание 2 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Ответ
97
Задание 3 Теория игр (3 хода) Открыть на доске →

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

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

- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ
12
Задание 4 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ
23
Задание 5 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Ответ
132
Задание 6 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ
29
Задание 7 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ
14
Задание 8 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ
30
Задание 9 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Ответ
52
Задание 10 Теория игр (3 хода) Открыть на доске →

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

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

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

Ответ
18
ИнфДоска

Разбирайте задание 21 ЕГЭ на онлайн-доске

Задание из банка — на доску в один клик, ответ видите только вы. После урока доска сама составит отчёт маме или папе.

Другие задания ЕГЭ