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

О чём задание

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

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

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

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

Задание 19: найти все значения S = S₁ + S₂ (или конкретно 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. Петя — первый игрок, поэтому «выигрышная позиция за 1 ход» = позиция, в которой Петя первым же ходом заканчивает игру.

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

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

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

Перебираем все 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 включительно. Это и есть все S, при которых у Пети есть выигрышная стратегия за один ход.

Ответ часто просят в виде списка или количества. Здесь — 25 значений.

Python-перебор

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

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)

answer = [s for s in range(1, N) if win_in_one(s)]
print(answer)           # [25, 26, ..., 49]
print(len(answer))      # 25

Короче не бывает. Если операции другие — меняешь список 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)

answer = [s2 for s2 in range(1, N) if win_in_one(S1, s2)]
print(answer)

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

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

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

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

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

Это уже логика заданий 20-21. Для 19 достаточно шага 1.

Полный шаблон 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 state(s, depth):
    """
    Возвращает:
      'W' — текущий игрок выигрывает
      'L' — текущий игрок проигрывает
    depth — ограничение на количество оставшихся ходов (для 19, 20)
    """
    if s >= N:
        return 'L'  # предыдущий игрок уже победил
    if depth == 0:
        return None  # не успеваем проверить
    results = [state(m(s), depth - 1) for m in moves]
    if 'L' in results:
        return 'W'
    return 'L'

Этот шаблон слегка общий, на экзамене его подправляют под конкретную формулировку. Но идея — одна.

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

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 минуты
Выписать операции на черновик	30 секунд
Написать Python-перебор	1-2 минуты
Запустить, проверить ответ	1 минута
Итого	4-6 минут

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

Связь с 20 и 21

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

• 19 — Петя выигрывает за 1 ход (кто? Петя; когда? сразу).
• 20 — Петя выигрывает за 1 или 2 хода (Ваня не может выиграть в 1 ход).
• 21 — Ваня выигрывает в любом случае (при любом первом ходе Пети у Вани есть стратегия выигрыша за 1 или 2 хода).

Если у тебя есть универсальный Python-шаблон с state(s, depth), все три задачи решаются в одном скрипте за 5 минут. Это 3 первичных балла за 15-20 минут — очень выгодный блок для тренировки.

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

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

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

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

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

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

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

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

Итоги

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

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