Задание 19: выигрышная стратегия — как искать нужное значение S

Задание 19 открывает серию из трёх задач (19–20–21), построенных на одной и той же игре — только вопросы к ней разные. Здесь два игрока по очереди меняют кучу камней, и нужно понять, при каком стартовом количестве камней конкретный игрок гарантированно побеждает. На первый взгляд это похоже на олимпиадную головоломку, но на самом деле задание проверяет умение перебрать конечное число вариантов и не запутаться в условии "любой ход" против "хотя бы один ход" — а это именно то, чем в реальном программировании являются циклы for внутри for.

Что нужно знать

Игра с полной информацией

Игры, которые встречаются в задании 19, — это игры с полной информацией: оба игрока в любой момент знают точное состояние кучи (сколько в ней камней) и все правила ходов. Здесь нет ни случайности (кубиков, карт), ни скрытых данных — значит, исход игры при правильной игре обеих сторон предопределён заранее, его можно вычислить.

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

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

Ключевое правило. Игрок выигрывает "первым ходом", если после этого хода куча достигает порогового значения (или превышает его) — партия останавливается, и последний сделавший ход побеждает.

Чем задача 1 отличается от задач 2 и 3

В серии 19–20–21 правила игры всегда одни и те же, различаются только вопросы:

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

Границы диапазона (например, "куча заканчивается при 129 или более камнях") и сами разрешённые ходы в разных вариантах ЕГЭ отличаются: где-то разрешено добавлять 1 или 4 камня, где-то — удваивать или утраивать кучу, иногда куч две, а не одна, и ход применяется только к одной из них. Логика решения от этого не меняется — меняется только формула хода.

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

Условие (в стиле реальных вариантов): Петя и Ваня играют в игру с кучей камней. Играющие ходят по очереди, первый ход делает Петя. За один ход можно добавить в кучу один камень или удвоить число камней в куче. Игра завершается, как только в куче окажется 33 или больше камней; выигрывает тот, кто сделал последний ход. Найдите такое значение S (число камней в начале игры), при котором Петя не может выиграть первым ходом, но Ваня выигрывает первым ходом при любом ходе Пети.

Подход к решению без программирования: сначала находим, при каких числах камней любой игрок выигрывает одним ходом — это числа x, для которых x+1 ≥ 33 или 2x ≥ 33, то есть x ≥ 17 (потому что 2·17 = 34 ≥ 33, а x+1 ≥ 33 нужно уже x ≥ 32, но условие "или" делает достаточным x ≥ 17). Дальше рассматриваем оба хода Пети — S+1 и 2S — и требуем, чтобы оба попадали в эту "выигрышную зону" x ≥ 17. Одновременно у самого S не должно быть выигрышного хода, то есть S+1 < 33 и 2S < 33.

Показать решение и ответ

Шаг 1. Условие "Петя не выигрывает первым ходом": S + 1 < 33 и 2S < 33. Второе неравенство сильнее: S < 16.5, значит S ≤ 16.

Шаг 2. Условие "Ваня выигрывает первым ходом при любом ходе Пети" означает, что оба возможных числа камней после хода Пети — это S+1 и 2S — должны быть числами x, из которых один ход доводит кучу до 33+. Мы показали выше, что это верно при x ≥ 17.

Шаг 3. Требуем 2S ≥ 17, то есть S ≥ 8.5 → S ≥ 9. И требуем S + 1 ≥ 17, то есть S ≥ 16.

Шаг 4. Пересечение всех условий: S ≤ 16 (шаг 1) и S ≥ 16 (шаг 3, более сильное ограничение). Единственное значение — S = 16.

Проверка. При S = 16 у Пети есть два хода: 16+1 = 17 или 16·2 = 32. Ни один не достигает 33, значит Петя не выигрывает сразу. Если Петя сходил в 17 — Ваня удваивает: 17·2 = 34 ≥ 33, победа. Если Петя сходил в 32 — Ваня добавляет камень: 32+1 = 33 ≥ 33, победа. Оба случая закрыты.

Ответ: S = 16.

Как решить в Python

def petya_wins_now(s, threshold):
    # Петя выигрывает первым ходом, если хотя бы один ход достигает порога
    return (s + 1) >= threshold or (s * 2) >= threshold

def vanya_wins_from(x, threshold):
    # Проверяем, может ли игрок выиграть одним ходом из позиции x
    return (x + 1) >= threshold or (x * 2) >= threshold

threshold = 33
answers = []

for s in range(1, threshold):
    if petya_wins_now(s, threshold):
        continue  # Петя уже выигрывает сам — не подходит по условию

    # Оба возможных хода Пети должны отдавать победу Ване
    move_add = s + 1
    move_double = s * 2
    if vanya_wins_from(move_add, threshold) and vanya_wins_from(move_double, threshold):
        answers.append(s)

print(answers)  # ожидаем [16]

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