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

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

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

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

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

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

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

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

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

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

Условие

Условия игры — как в задании 19: добавить один камень или удвоить кучу, игра заканчивается при 50 и более камнях, 1 ≤ S ≤ 49. Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Решение

Из задания 19 знаем: S = 24 — проигрышная позиция для того, кто ходит. Значит, Петя выигрывает вторым ходом, если может первым ходом получить 24: S = 23 (+1) и S = 12 (×2). Ответ: 12 23.

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(*[s for s in range(1, 50) if game(s) == ('W', 2)][:2])
Код на Python 3 — его можно запустить прямо на ИнфДоске.
Ответ: 12 23

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

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

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

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

– Петя не может выиграть за один ход;

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

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

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

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

- Петя не может выиграть за один ход;

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

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

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

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

- Петя не может выиграть за один ход;

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

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

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

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

– Петя не может выиграть за один ход;

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

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

Ответ
14,24
Задание 5 Теория игр (2 хода) Открыть на доске →

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

– Петя не может выиграть за один ход;

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

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

Ответ
127,128
Задание 6 Теория игр (2 хода) Открыть на доске →

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

- Петя не может выиграть за один ход;

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

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

Ответ
30,33
Задание 7 Теория игр (2 хода) Открыть на доске →

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

- Петя не может выиграть за один ход;

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

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

Ответ
15,18
Задание 8 Теория игр (2 хода) Открыть на доске →

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

– Петя не может выиграть за один ход;

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

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

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

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

– Петя не может выиграть за один ход;

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

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

Ответ
47,48
Задание 10 Теория игр (2 хода) Открыть на доске →

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

– Петя не может выиграть за один ход;

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

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

Ответ
10,19
ИнфДоска

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

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

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