Как решать задание 19 ЕГЭ по информатике — теория игр, выигрыш Вани первым ходом

О чём задание

Задание 19 открывает блок теории игр в ЕГЭ по информатике (19, 20, 21 — все про одну и ту же игру). Базовая постановка примерно такая:

На столе две кучи камней. В первой S₁ камней, во второй S₂ камней. Игроки Петя и Ваня ходят по очереди, первым ходит Петя. За один ход можно:

• прибавить к одной из куч 1 камень,
• прибавить к одной из куч 2 камня,
• удвоить количество камней в одной из куч.

Игра заканчивается, когда общее количество камней становится не меньше N. Побеждает игрок, сделавший последний ход.

Задание 19: укажите минимальное значение S₂ (S₁ зафиксировано), при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Существует масса вариантов: одна куча или две, операции +1, +2, ×2, +1, ×2, ×3, условие окончания «≥ N» или «> N», побеждает делающий последний ход или делающий ход, приводящий к фиксированному значению. Суть одна: надо перебрать позиции и понять, какие из них выигрышные.

Ключевые понятия

Выигрышная позиция

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

Проигрышная позиция

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

Конечная позиция

Позиция, где условие окончания уже выполнено (например, сумма ≥ N). Она не «выигрышная» и не «проигрышная» в смысле выше — в ней просто никто уже не ходит. Для анализа эти позиции — это результат хода, который приводит к победе того, кто только что ходил.

Стратегия «за один ход» — что это конкретно

Вся задача 19 собирается из одной проверки. «Игрок выигрывает за один ход» означает:

Существует хотя бы одна операция (из разрешённых), которая из позиции (S₁, S₂) сразу приводит к окончанию игры.

Если условие окончания — сумма ≥ N, то:

• ход +1 выигрывает, если (S₁ + 1) + S₂ ≥ N, то есть S₁ + S₂ ≥ N − 1
• ход +2 выигрывает, если S₁ + S₂ ≥ N − 2
• ход ×2 выигрывает, если 2·S₁ + S₂ ≥ N или S₁ + 2·S₂ ≥ N

Для задачи с одной кучей проще: ход выигрывает, если после его применения к S получится значение ≥ N.

В задании 19 эта проверка применяется дважды. Сначала — к стартовой позиции: у Пети хода-победителя быть не должно. Затем — к каждой позиции, которая получается после хода Пети: там выиграть одним ходом должен уже Ваня. Если оба условия выполнены, значение S подходит; в ответ идёт минимальное из подходящих.

Разбор на конкретном примере

Пусть условие такое:

В куче S камней (1 ≤ S < 50). За ход разрешено прибавить 1, прибавить 2 или удвоить количество камней. Игра заканчивается при S ≥ 50. Укажите минимальное S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня выигрывает своим первым ходом.

Шаг 1: находим позиции с выигрышем за один ход. Перебираем все S от 49 до 1 и проверяем: существует ли ход, приводящий к S' ≥ 50?

S	S+1	S+2	S×2	Выигрыш за 1 ход?
49	50	51	98	Да
48	49	50	96	Да
47	48	49	94	Да
46	47	48	92	Да
...
25	26	27	50	Да
24	25	26	48	Нет

Из таблицы видно: ход ×2 выигрывает, если S ≥ 25. Ход +2 выигрывает, если S ≥ 48. Ход +1 — если S ≥ 49.

Объединение: S от 25 до 49 включительно. Из любой из этих позиций игрок, чей сейчас ход, заканчивает игру немедленно.

Шаг 2: ищем позицию Пети. Нужно S ≤ 24 (иначе Петя выиграл бы сам), из которого все три хода — S+1, S+2 и 2·S — попадают в диапазон 25–49, где Ваня выигрывает одним ходом. Самое жёсткое из условий — S+1 ≥ 25, то есть S ≥ 24. Вместе с S ≤ 24 остаётся единственное значение. Проверяем S = 24: ходы дают 25, 26 и 48, и из каждой из этих позиций Ваня заканчивает игру. Ответ: 24.

Python-перебор

Полный код для проверки этого примера — около десяти строк:

N = 50
moves = [lambda s: s + 1, lambda s: s + 2, lambda s: s * 2]

def win_in_one(s):
    return any(m(s) >= N for m in moves)

def task19(s):
    # Петя не выигрывает за 1 ход, но любой его ход отдаёт выигрыш Ване
    return not win_in_one(s) and all(m(s) < N and win_in_one(m(s)) for m in moves)

answer = [s for s in range(1, N) if task19(s)]
print(min(answer))      # 24

Если операции другие — меняешь список moves. Если условие окончания другое (например, > N, а не ≥ N), правишь сравнение в win_in_one.

Две кучи

Для варианта с двумя кучами проверка выигрыша за один ход почти такая же:

N = 50
S1 = 7  # зафиксировано в условии

def win_in_one(s1, s2):
    moves = [
        (s1 + 1, s2), (s1, s2 + 1),
        (s1 + 2, s2), (s1, s2 + 2),
        (2 * s1, s2), (s1, 2 * s2),
    ]
    return any(a + b >= N for a, b in moves)

# стартовые позиции, где S1 + s2 >= N, исключаем:
# там условие окончания выполнено ещё до первого хода
win1 = [s2 for s2 in range(1, N - S1) if win_in_one(S1, s2)]
print(win1)             # [22, 23, ..., 42]

Главное — корректно перечислить все возможные ходы. Если операция применима к любой из двух куч, то для каждой операции получается два варианта хода. Шаг 2 навешивается сверху так же, как в примере с одной кучей: ищешь s₂, при котором win_in_one ложна для позиции Пети, но истинна после каждого его хода.

Обратный ход и таблица позиций (для 20 и 21)

Для задания 19 полная таблица позиций не нужна — хватает двух применений проверки «есть ли выигрыш за 1 ход». Но для 20 (Петя выигрывает вторым ходом) и 21 (Ваня выигрывает первым или вторым) пригодится метод backward induction.

Идея: идём от финальных позиций назад и помечаем каждую как выигрышную или проигрышную:

1. Позиция, из которой хотя бы один ход сразу заканчивает игру, — выигрышная за 1 ход. Помечаем её W1.
2. Позиция, из которой любой ход ведёт в позицию W1 (то есть соперник после твоего хода выигрывает одним ходом), — проигрышная. Помечаем её L1.

Дальше правило повторяется: позиция выигрышная, если существует ход в проигрышную; проигрышная — если все ходы ведут в выигрышные. Это уже логика заданий 20-21. Для 19 хватает шагов 1 и 2: ответ задания — наименьшая позиция L1.

Базовый шаблон Python для всего блока 19-20-21

from functools import lru_cache

N = 50
moves = [lambda s: s + 1, lambda s: s + 2, lambda s: s * 2]

@lru_cache(maxsize=None)
def wins(s):
    """True, если игрок, делающий ход из позиции s, выигрывает при оптимальной игре."""
    if s >= N:
        return False   # игра уже окончена: ходить некому, победил предыдущий игрок
    return any(not wins(m(s)) for m in moves)

Читается формула так: текущий игрок выигрывает, если найдётся ход, после которого сопернику ходить из проигрышной позиции. Для заданий 19 и 20 к этой заготовке добавляется ограничение на число ходов из формулировки («за один ход», «за два хода») — на экзамене подправь функцию под конкретное условие.

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

1. Перепутан порядок ходов

В ЕГЭ всегда первым ходит Петя. Некоторые по ошибке начинают с Вани — и все результаты переворачиваются. Проверяй условие дважды.

2. Забыл одну из операций

Если в условии три операции (+1, +2, ×2), а ты забыл третью — пропустишь половину выигрышных позиций. Всегда выписывай операции на черновик перед запуском перебора.

3. Путаница «≥ N» и «> N»

«Игра заканчивается при сумме не меньше N» — это ≥ N. «Игра заканчивается при сумме больше N» — это > N. Разница в один элемент, но ответ может поехать. Читай внимательно.

4. Неверный диапазон перебора

Если ищешь все S от 1 до N−1, помни: range(1, N) в Python — это от 1 до N−1 включительно. Проверь границы для своего случая. Некоторые задачи задают 1 ≤ S ≤ N−1, некоторые — 0 ≤ S.

5. Ход к «не той» куче

В варианте с двумя кучами важно, что операция применяется к одной выбранной куче, а не к обеим. Если ты в коде написал (s1 + 1, s2 + 1) — ты фактически описал другую игру, где ход меняет обе кучи сразу.

6. Перечислил операции как кортежи, а не ходы

Иногда в условии написано «можно прибавить 1 или 2 камня». Это две разные операции, не одна с выбором. В коде нужны оба варианта в списке moves, иначе половина ходов пропадёт.

Тайминг

Этап	Время
Прочитать условие и понять, что именно спрашивают	2-3 минуты
Выписать операции на черновик	1 минута
Написать Python-перебор	3-4 минуты
Запустить, проверить ответ по условию	2 минуты
Итого	8-10 минут

На фоне соседей это самый быстрый номер блока: на 20 уходит 10-12 минут, на 21 — 12-15, а весь блок 19-21 занимает 30-40 минут.

Если пишешь перебор руками (без Python), добавь 2-3 минуты на таблицу и перепроверку. Но на практике Python всё равно быстрее и надёжнее. Это одна из тех задач, где Python-подход серьёзно экономит время — подробнее в статье Python или C++ для ЕГЭ.

Связь с 20 и 21

Задания 19, 20, 21 — это одна игра с тремя вопросами:

• 19 — Петя не может выиграть за 1 ход, но любой его ход даёт Ване выигрыш первым ходом (ответ — минимальное S).
• 20 — Петя не может выиграть за 1 ход, но выигрывает своим вторым ходом при любой игре Вани (ответ — два наименьших S).
• 21 — Ваня выигрывает первым или вторым ходом при любой игре Пети, но не может гарантировать выигрыш первым ходом (ответ — минимальное S).

Если у тебя есть универсальный Python-шаблон — например, функция wins из раздела выше, дополненная подсчётом числа ходов, — все три задачи решаются в одном скрипте: код пишешь один раз, а дальше меняешь только проверку под вопрос. Это 3 первичных балла за 30-40 минут — очень выгодный блок для тренировки.

Вариации условий, которые встречаются

Под одну и ту же идею подгоняются разные формулировки. Вот что может измениться:

• Количество куч — 1 или 2 (реже 3).
• Операции — +1, +2, +1, ×2, +1, ×2, ×3, ×2, ×3.
• Условие окончания — сумма ≥ N, сумма > N, в одной куче ≥ N.
• Кто выигрывает — «сделавший последний ход» или «сделавший ход, при котором условие выполнилось» (в 99% случаев это то же самое).
• Начальные условия — фиксированы одна куча или обе, варьируется одна.

Шаблон moves легко подстраивается. Главное — не проспать нюансы в чтении условия.

Чек-лист на экзамене

Перед написанием кода пройдись по этому списку:

• Сколько куч?
• Какие операции разрешены? (Выпиши все!)
• Условие окончания — ≥ N или > N? Значение N?
• Кто первым ходит? (Петя — всегда, но проверь.)
• Что именно спрашивают? (19 — Ваня выигрывает первым ходом после неудачного хода Пети; 20 — Петя выигрывает вторым ходом; 21 — Ваня выигрывает первым или вторым.)
• В каком формате ответ? (Минимальное значение, два наименьших, список.)

Если хотя бы один пункт вызывает сомнение — перечитай условие. Неправильно понял его — получишь за задачу ноль, даже если код написан без ошибок.

Итоги

• Задание 19 — теория игр, начало блока 19-20-21.
• Вопрос 19: минимальное S, при котором Петя не может выиграть за один ход, но любой его ход даёт Ване выигрыш первым ходом.
• Базовая проверка одна — «есть ли ход, сразу заканчивающий игру»; она применяется к позиции Пети и к позициям после его ходов.
• Ключевые понятия: выигрышная и проигрышная позиция, backward induction.
• Решение на Python — около десяти строк кода с перебором всех операций.
• Рекомендуемое время — 8-10 минут.
• Стоимость — 1 первичный балл; вместе с 20-21 даёт 3 балла за 30-40 минут.
• Типичные ошибки: забыл операцию, перепутал ≥ и >, перепутал порядок игроков.

Разобрался с 19 — легко берёшь 20 и 21. Это один из самых тренируемых и предсказуемых блоков в ЕГЭ. Как тренировать задачи по блокам, подробно.

Задачи всего блока 19–21 есть в TuteMe с автопроверкой: разные наборы ходов, одна и две кучи, а после ошибки показывается разбор с таблицей позиций.

Попробовать бесплатно →