Задание 19 ЕГЭ по информатике: теория игр, неудачный ход Пети — разбор и примеры

Задания 19, 20 и 21 — это одна игра и три вопроса к ней. Условие общее: двое игроков, Петя и Ваня, по очереди меняют кучу (или две кучи) камней по заданным правилам; побеждает тот, после чьего хода камней стало не меньше заданного числа. Задание 19 — самое простое из трёх: в нём нужно найти позицию, где Ваня выигрывает первым же ходом, если Петя походил неудачно. Его можно решить и вручную, и программой, но шаблон на Python полезно освоить сразу — он же решит 20 и 21.

Что проверяет задание

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

Терминология: позиция — количество камней в куче (или пара чисел для двух куч) перед очередным ходом. Стратегия — правило, говорящее, какой ход сделать в каждой позиции. «Неудачный» ход — любой ход, после которого соперник получает возможность выиграть.

Типичные формулировки

1. Одна куча, ходы «добавить один камень», «добавить несколько камней», «увеличить в два раза»; игра заканчивается, когда в куче не меньше S камней. Спрашивают минимальное начальное значение, при котором Ваня мог выиграть первым ходом после неудачного хода Пети.
2. Две кучи: за ход можно увеличить одну из куч на 1 или в два раза; игра заканчивается, когда суммарно камней не меньше заданного числа. Вопрос тот же.
3. Вариант «Петя не может выиграть за один ход, но Ваня может выиграть первым ходом при любом ходе Пети» — это уже проигрышная позиция для Пети (тип П1), её иногда тоже спрашивают в задании 19.

Важно различать формулировки: «после неудачного хода» означает, что достаточно одного хода Пети, ведущего к выигрышу Вани. «При любом ходе Пети» — нужно, чтобы все ходы Пети вели к выигрышу Вани.

Пошаговый метод

1. Выпишите ходы и условие окончания. Например: из s можно получить s + 1, s + 4 или 2s; игра заканчивается при s ≥ 57.
2. Найдите позиции «выигрыш в один ход» (В1). Это все s, из которых хотя бы один ход даёт не меньше цели. При ходе «удвоить» это s ≥ 29 (так как 2 · 29 = 58).
3. Переберите начальные значения по возрастанию. Для каждого S посмотрите, есть ли ход Пети в позицию В1 (которая сама ещё не конец игры). Первое такое S — ответ.
4. Проверьте граничное значение на 1 меньше — убедитесь, что у него ни один ход в В1 не ведёт.
5. Запишите ответ одним числом.

Разбор примера 1 (одна куча)

Ходы: добавить 1 камень, добавить 4 камня или удвоить кучу. Игра заканчивается, когда в куче не меньше 57 камней. Сначала в куче S камней, 1 ≤ S ≤ 56, первым ходит Петя. Найдите минимальное S, при котором Ваня мог выиграть своим первым ходом после неудачного первого хода Пети.

Позиции В1. Из позиции s можно выиграть одним ходом, если 2s ≥ 57 (то есть s ≥ 29) или s + 4 ≥ 57 (s ≥ 53). Значит, В1 — это все s от 29 до 56.

Ищем S. Нужно, чтобы какой-то ход Пети приводил в позицию от 29 до 56. Самый «большой» ход — удвоение: 2S ≥ 29, то есть S ≥ 15 (14 · 2 = 28 — мало, а 14 + 4 = 18 и 14 + 1 = 15 тоже меньше 29).

Проверка S = 15. Петя удваивает: 15 → 30. Ваня удваивает: 30 → 60 ≥ 57 — Ваня выиграл первым ходом. Ход Пети был неудачным: например, ход 15 → 19 таким не был бы.

Ответ: 15.

Разбор примера 2 (две кучи)

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

Выгоднее всего для Вани удвоить большую кучу. Если Петя удвоил вторую кучу, получилось (5, 2S), и Ване достаточно, чтобы 5 + 4S ≥ 45, то есть S ≥ 10. Проверка S = 10: Петя делает (5, 20), Ваня удваивает вторую кучу — (5, 40), сумма 45, Ваня выиграл. При S = 9 лучший вариант Пети для Вани — (5, 18), откуда максимум 5 + 36 = 41 < 45, а другие ходы дают ещё меньше. Ответ: 10.

Код на Python: общий шаблон для заданий 19–21

Функция result(s) классифицирует позицию: ('W', k) — ходящий выигрывает своим k-м ходом при правильной игре, ('L', k) — ходящий проигрывает, а соперник выигрывает не позже своего k-го хода. Выигрывающий стремится выиграть как можно быстрее, проигрывающий — затянуть игру.

from functools import lru_cache

GOAL = 57                       # игра заканчивается, когда камней не меньше 57

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

@lru_cache(None)
def result(s):
    nxt = moves(s)
    if any(x >= GOAL for x in nxt):
        return ('W', 1)
    res = [result(x) for x in nxt]
    lose = [k for t, k in res if t == 'L']
    if lose:                     # есть ход в проигрышную для соперника позицию
        return ('W', min(lose) + 1)
    return ('L', max(k for t, k in res))

# Задание 19: есть ход Пети в позицию, где Ваня выигрывает одним ходом
ans = [s for s in range(1, GOAL)
       if any(x < GOAL and result(x) == ('W', 1) for x in moves(s))]
print(min(ans))                  # 15

Для двух куч позиция — кортеж (a, b), а moves возвращает четыре варианта: (a + 1, b), (2a, b), (a, b + 1), (a, 2b). Условие окончания — сумма не меньше цели. Остальное не меняется.

Частые ошибки

• Путают «неудачный ход» и «любой ход». В задании 19 про неудачный ход достаточно существования одного плохого хода Пети.
• Забывают, что позиция после хода Пети не должна быть концом игры. Если Петя своим ходом уже достиг цели, выигрывает он, а не Ваня; в программе это условие x < GOAL.
• Ошибаются в границе «не меньше». Проверяйте >=, а не >.
• Не проверяют значение на единицу меньше ответа. Минимальность нужно подтвердить.
• Для двух куч удваивают не ту кучу. Ване выгоднее удвоить большую кучу, Пете при «неудачном» ходе — подготовить её.
• Забывают про lru_cache. Без запоминания программа для двух куч может работать очень долго.

Потренируйтесь

Решите задачи из задания № 19 в банке, меняя в шаблоне только moves и GOAL. Теория выигрышных и проигрышных позиций подробно — в статье «Игры с выигрышными и проигрышными позициями». Следующий вопрос той же игры — задание 20: Петя выигрывает вторым ходом.