Question

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

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

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

Игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

Accepted Answer

19

Answer

Идея решения: найти позицию, из которой первый игрок не может сразу выиграть, но любой его ход ведёт в позицию, из которой второй игрок гарантированно выигрывает. Сначала определим, из каких позиций можно выиграть за один ход. Это позиции в диапазоне $[20; 39]$: удвоив кучу, получим не менее 40 камней и сразу победим. Теперь найдём позицию, из которой все возможные ходы ведут в выигрышные для противника позиции. Из позиции 19: - добавить 1 → 20 (выигрышная для противника); - добавить 4 → 23 (выигрышная для противника); - удвоить → 38 (выигрышная для противника). Все три хода Пети приводят в диапазон $[20; 39]$, откуда Ваня может удвоить и выиграть. При этом сам Петя не может выиграть первым ходом (максимум получит 38 < 40). Проверим соседние позиции: - Из 18: удвоение даёт 36 (не выигрыш), но добавление 4 даёт 22 (выигрыш для противника). Однако не все ходы ведут в выигрышные позиции. - Из 20: удвоение даёт 40 — Петя выигрывает сразу. Таким образом, $S = 19$ — единственная позиция, удовлетворяющая условиям. Проверим с помощью рекурсивной функции: ```python def f(x, h): if h == 3 and x >= 40: return 1 elif h == 3 and x < 40: return 0 elif x >= 40 and h < 3: return 0 else: if h % 2 == 0: return (f(x + 1, h + 1) or f(x + 4, h + 1) or f(x * 2, h + 1)) else: return (f(x + 1, h + 1) and f(x + 4, h + 1) and f(x * 2, h + 1)) for x in range(1, 40): if f(x, 1) == 1: print(x) break ``` Функция возвращает 1, если первый игрок (Петя) имеет выигрышную стратегию. При чётном ходе (Петя) ищется хотя бы один выигрышный ход; при нечётном (Ваня) проверяется, что все его ходы ведут в выигрышные позиции для Пети. Условие $h = 3$ означает, что мы проверяем позицию после второго хода Пети.

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