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

Задание 21 завершает тройку заданий по теории игр. Игра та же, что в заданиях 19 и 20, но теперь выигрышная стратегия есть у Вани — второго игрока. Нужно найти начальную позицию, в которой Ваня гарантированно выигрывает своим первым или вторым ходом при любой игре Пети, но не может гарантировать победу именно первым ходом. Формулировка длинная, и большинство ошибок здесь — от неточного прочтения.

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

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

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

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

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

1. Найдите В1 — позиции, из которых можно выиграть одним ходом.
2. Найдите П1 — позиции вне В1, у которых все ходы ведут в В1.
3. Найдите В2 — позиции вне В1, у которых есть ход в П1.
4. Найдите П2 — позиции вне В1 и П1, у которых все ходы ведут в В1 или В2, причём хотя бы один ход ведёт в В2. Именно второе условие гарантирует, что Ваня не всегда выигрывает первым ходом.
5. Выберите нужное значение (обычно минимальное) и проверьте его по всем ходам Пети.

Разбор примера

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

В1 — s от 29 до 56 (удвоение даёт не меньше 57).

П1 — {28}: все ходы 29, 32, 56 ведут в В1, а сам 28 выиграть не может.

В2 — {14, 24, 27}: из каждой позиции есть ход в 28 (подробно — в разборе задания 20).

П2. Ищем s ≤ 27, не входящие в В2, у которых все три хода попадают в В1 или В2. Проверим кандидатов, у которых хотя бы один ход ведёт в В2:

• s = 23: ходы 24 (В2), 27 (В2), 46 (В1) — все выигрышные для Вани, подходит;
• s = 26: ходы 27 (В2), 30 (В1), 52 (В1) — тоже подходит;
• s = 13: ходы 14 (В2), 17, 26 — позиция 17 не входит ни в В1, ни в В2, не подходит;
• s = 20: ходы 21, 24, 40 — позиция 21 не выигрышная для Вани за два хода, не подходит.

Минимальное значение — 23. Проверим обе части условия.

Ваня выигрывает не позже второго хода. Если Петя удвоит кучу (23 → 46), Ваня сразу удваивает: 92 ≥ 57. Если Петя сделает 24 или 27, Ваня ходит в 28 (24 + 4 или 27 + 1), и Петя оказывается в П1: любой его ход даёт Ване победу следующим ходом.

Гарантии выигрыша первым ходом нет. Если Петя пойдёт в 24, Ваня не может выиграть сразу: максимум 48 < 57.

Ответ: 23.

Код на Python

Шаблон общий для заданий 19–21. Тип ('L', 2) — ровно позиция П2: ходящий (Петя) проигрывает, соперник (Ваня) выигрывает не позже своего второго хода, а раз число равно 2, а не 1, гарантированно выиграть первым ходом нельзя.

from functools import lru_cache

GOAL = 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))

ans = [s for s in range(1, GOAL) if result(s) == ('L', 2)]
print(ans, min(ans))            # [23, 26] 23

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

Дерево игры: как оформить проверку

На черновике удобно нарисовать дерево игры для найденного значения. В корне — начальная позиция 23, из неё три ветви — все ходы Пети: 24, 27 и 46. Под позицией 46 достаточно одного листа — выигрышного хода Вани. Под позициями 24 и 27 пишем по одному ходу Вани (в позицию 28), а под 28 — все три хода Пети и выигрышный ответ Вани на каждый. Правило построения простое: в узлах, где ходит Петя, перечисляются все ходы, а в узлах, где ходит Ваня, — один ход его стратегии. Если дерево удалось достроить так, что все листья — победы Вани не позже второго хода, а хотя бы один лист находится на глубине второго хода, ответ верен.

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

• Выбирают позицию П1. В ней Ваня всегда выигрывает первым ходом — это противоречит второй части условия.
• Проверяют только один ход Пети. Стратегия Вани должна работать при любом ходе Пети: проверяйте все ходы.
• Путают П2 с позициями, где Ваня выигрывает третьим ходом. Если хоть один ход Пети ведёт в позицию, откуда Ване нужно три хода, значение не подходит.
• Ищут минимальное S, а условие просит максимальное (или наоборот). Перечитайте вопрос.
• Неверно считают условие окончания для двух куч. Цель — сумма камней в обеих кучах, если не сказано иное.

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

Закрепите шаблон на заданиях № 21 в банке: для каждой игры решайте сразу 19, 20 и 21 — это экономит время на экзамене. Повторить вопросы о Пете можно в разборе задания 20, а дальше по порядку — задание 22: параллельные процессы.