Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока есть неограниченное количество камней для ходов.

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

В начальный момент в куче было $S$ камней; $1 \le S \le 42$.

Найдите минимальное значение $S$, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, позволяющей гарантированно выиграть первым ходом.

Accepted Answer

18

Answer

Идея решения: построить рекурсивную функцию, которая определяет, может ли текущий игрок выиграть за заданное количество своих ходов, и найти минимальное начальное значение, при котором второй игрок (Ваня) выигрывает за два хода, но не за один. Функция `f(x, h)` возвращает 1, если игрок, чей ход сейчас, может выиграть за оставшееся количество ходов, и 0 иначе. Параметр `x` — текущее количество камней, `h` — номер хода (нечётные ходы — Петя, чётные — Ваня). Базовые случаи: - Если $h = 3$ или $h = 5$ (ходы Вани) и $x \ge 43$, Ваня выиграл. - Если $h = 5$ и $x < 43$, Ваня не может выиграть за два своих хода. - Если $x \ge 43$ и $h < 5$, текущий игрок уже проиграл (соперник выиграл раньше). Рекурсивные случаи: - На ходу игрока (чётный $h$) — нужно, чтобы существовал хотя бы один выигрышный ход (дизъюнкция). - На ходу соперника (нечётный $h$) — все его ходы должны вести в проигрышную позицию для него (конъюнкция). ```python def f(x, h): if (h == 3 or h == 5) and x >= 43: return 1 elif h == 5 and x < 43: return 0 elif x >= 43 and h < 5: return 0 else: if h % 2 == 0: return (f(x + 1, h + 1) or f(x + 2, h + 1) or f(x * 2, h + 1)) else: return (f(x + 1, h + 1) and f(x + 2, h + 1) and f(x * 2, h + 1)) for x in range(1, 43): if f(x, 1) == 1: print(x) ``` Проверим логику для $S = 18$: - Петя может получить позиции 19, 20 или 36. - При $x = 36$: Ваня удваивает → 72 ≥ 43, Ваня выигрывает на ходу 2. - При $x = 20$: Ваня добавляет 1 → 21. Петя может получить 22, 23 или 42. При любом ходе Пети Ваня добавляет камни и достигает ≥ 43 на ходу 4. - При $x = 19$: Ваня добавляет 2 → 21. Аналогично, Ваня выигрывает на ходу 4. Таким образом, Ваня гарантированно выигрывает за два своих хода (ходы 2 и 4), но не может выиграть на ходу 2 при всех начальных позициях.

Задание №21Алгоритмы и исполнителиЕГЭ по информатике