Question

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

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

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

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

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

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

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

Accepted Answer

29

Answer

Идея решения: найти позицию, из которой первый игрок не может сразу выиграть, но любой его ход приводит в позицию, из которой второй игрок гарантированно выигрывает за один ход. Обозначим позицию выигрышной для текущего игрока, если он может выиграть при любых ходах противника. Позиция выигрышна за один ход, если существует ход, переводящий кучу в состояние $\geq 88$. Проверим, какие позиции позволяют выиграть за один ход: - Добавить 1: нужно $x \geq 87$, то есть $x = 87$. - Добавить 4: нужно $x \geq 84$, то есть $x \in [84, 87]$. - Умножить на 3: нужно $x \geq 30$ (так как $3 imes 29 = 87 < 88$, а $3 imes 30 = 90 \geq 88$). Итак, позиция выигрышна за один ход, если $x \in [30, 87]$. Нам нужна позиция $S$, такая что: 1. $S otin [30, 87]$ (Петя не выигрывает за один ход). 2. Все ходы Пети из $S$ приводят в позиции, из которых Ваня выигрывает за один ход. Проверим $S = 29$: - Петя может добавить 1: получит 30 (Ваня выигрывает за один ход). - Петя может добавить 4: получит 33 (Ваня выигрывает за один ход). - Петя может умножить на 3: получит 87 (Ваня выигрывает за один ход). Все три хода Пети приводят в диапазон $[30, 87]$, откуда Ваня выигрывает за один ход. Проверим соседние значения: - $S = 28$: Петя может получить 29 (не выигрышная позиция за один ход), поэтому не подходит. - $S = 30$: Петя сразу выигрывает за один ход (умножить на 3 → 90), не подходит. Альтернативное решение на Python: ```python def can_win(x, depth): if depth == 3 and x >= 88: return True elif depth == 3 and x < 88: return False elif x >= 88 and depth < 3: return False else: if depth % 2 == 1: # ход Пети (нечётная глубина) return (can_win(x + 1, depth + 1) or can_win(x + 4, depth + 1) or can_win(x * 3, depth + 1)) else: # ход Вани (чётная глубина) return (can_win(x + 1, depth + 1) and can_win(x + 4, depth + 1) and can_win(x * 3, depth + 1)) for s in range(2, 87): if not can_win(s, 1): continue # Проверяем, что все ходы Пети приводят к выигрышу Вани moves = [s + 1, s + 4, s * 3] if all(can_win(m, 2) for m in moves): print(s) break ```

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