Question

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

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

Начальное количество камней: $1 \le S \le 88$. Игрок имеет выигрышную стратегию, если может гарантировать победу при любых ходах противника.

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

Accepted Answer

28

Answer

Идея решения: используем рекурсивный анализ позиций с учётом хода (чётный ход — выигрышная позиция для текущего игрока, нечётный — проигрышная), где позиция считается выигрышной, если текущий игрок может гарантировать победу. Определим функцию `f(x, h)`, где `x` — количество камней, `h` — номер хода (1 для Пети, 2 для Вани и т. д.): - Если `h == 3` (ход Пети на третьем ходу) и `x >= 89`, то Ваня выиграл на ходе 2 — возвращаем 1. - Если `h == 3` и `x < 89`, то Ваня не выиграл — возвращаем 0. - Если `x >= 89` и `h < 3`, то кто-то уже выиграл раньше — возвращаем 0. - Для чётного хода (Ваня): позиция выигрышная, если существует хотя бы один ход, ведущий к выигрышу (логическое ИЛИ). - Для нечётного хода (Петя): позиция выигрышная, если все его ходы ведут к выигрышу (логическое И). ```python def f(x, h): if h == 3 and x >= 89: return 1 elif h == 3 and x < 89: return 0 elif x >= 89 and h < 3: return 0 else: if h % 2 == 0: return (f(x + 2, h + 1) or f(x + 3, h + 1) or f(x * 3, h + 1)) else: return (f(x + 2, h + 1) and f(x + 3, h + 1) and f(x * 3, h + 1)) for x in range(1, 89): if f(x, 1) == 1: print(x) break ``` Проверим значение $S = 28$: - Петя может получить: $28 + 2 = 30$, $28 + 3 = 31$ или $28 imes 3 = 84$. - Из позиции 30: Ваня получает $30 imes 3 = 90 \ge 89$ — выигрыш. - Из позиции 31: Ваня получает $31 imes 3 = 93 \ge 89$ — выигрыш. - Из позиции 84: Ваня получает $84 imes 3 = 252 \ge 89$ — выигрыш. При $S = 27$: Петя может получить 29, 30 или 81. Из 29 Ваня получает 87 (не выигрыш), поэтому Петя может выиграть за один ход.

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