Question

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

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

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

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

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

Accepted Answer

21

Answer

Идея решения: найти позицию, из которой первый игрок не может сразу выиграть, но любой его ход приводит в позицию, из которой второй игрок гарантированно выигрывает за один ход. Проанализируем, при каких значениях $S$ игрок может выиграть за один ход. Это возможно, если существует ход, переводящий кучу в состояние $\ge 43$: - добавить 1: $S + 1 \ge 43 \Rightarrow S \ge 42$; - добавить 2: $S + 2 \ge 43 \Rightarrow S \ge 41$; - удвоить: $2S \ge 43 \Rightarrow S \ge 22$ (так как $2 \cdot 21 = 42 < 43$, $2 \cdot 22 = 44 \ge 43$). Значит, при $S \in \{22, 23, \ldots, 42\}$ первый игрок выигрывает за один ход. Теперь найдём позицию, из которой Петя не выигрывает за один ход, но все его ходы ведут в выигрышные для Вани позиции. Проверим $S = 21$: - Петя может добавить 1: получит 22 (выигрышная позиция для Вани). - Петя может добавить 2: получит 23 (выигрышная позиция для Вани). - Петя может удвоить: получит 42 (выигрышная позиция для Вани). Все ходы Пети приводят в позиции, из которых Ваня выигрывает за один ход. Проверим меньшие значения. При $S = 20$: - Петя может удвоить: получит 40. Ваня может добавить 2 и получить 42 (не выигрыш). Ваня может удвоить и получить 80 (выигрыш). Но нужно проверить, может ли Ваня выиграть при любом ходе Пети. - Петя может добавить 1: получит 21. Ваня может удвоить и получить 42 (не выигрыш). Ваня может добавить 1 и получить 22 (выигрыш). Ваня может добавить 2 и получить 23 (выигрыш). При $S = 20$ не все ходы Пети гарантируют выигрыш Вани за один ход (например, если Петя получит 40, Ваня не может выиграть за один ход, добавив 2). Таким образом, $S = 21$ — единственное значение, удовлетворяющее условию. Проверка с помощью рекурсивной функции: ```python def can_win(stones, is_first_player): if stones >= 43: return False moves = [stones + 1, stones + 2, stones * 2] if is_first_player: # Первый игрок выигрывает, если хотя бы один ход ведёт к выигрышу for next_stones in moves: if next_stones >= 43 or not can_win(next_stones, False): return True return False else: # Второй игрок выигрывает, если все ходы первого ведут к его выигрышу for next_stones in moves: if next_stones < 43 and can_win(next_stones, True): return False return True for s in range(1, 43): if not can_win(s, True): # Петя не выигрывает за один ход all_vanya_wins = True for move in [s + 1, s + 2, s * 2]: if move < 43 and not can_win(move, False): all_vanya_wins = False break if all_vanya_wins: print(s) break ```

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