Question

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

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

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

Выигрышная стратегия игрока — это описание ходов, при которых он выигрывает при любых ответах противника.

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

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Accepted Answer

1920

Answer

Идея решения: найти позиции, из которых первый игрок не выигрывает за один ход, но гарантирует победу на втором ходу, приводя противника в позицию, из которой тот не может избежать проигрыша. Обозначим позицию как выигрышную для текущего игрока, если он может выиграть при оптимальной игре. Проанализируем позиции с конца игры. Позиция выигрышна за один ход, если существует ход, приводящий к куче с числом камней $\ge 43$. Позиция выигрышна за два хода для первого игрока, если: 1. Первый игрок не может выиграть за один ход. 2. После хода первого игрока любой ход второго игрока приводит к позиции, из которой первый выигрывает за один ход. Проверим позиции $S < 21$. Если $S \ge 21$, то Ваня может удвоить кучу и получить $\ge 42$ камней, либо добавить камни и достичь $\ge 43$, выигрывая за один ход. Для $S = 19$: - Петя добавляет 2 камня → куча становится 21. - Ваня может: добавить 1 (→ 22), добавить 2 (→ 23) или удвоить (→ 42). - При любом ходе Вани куча содержит от 22 до 42 камней. - Петя добавляет камни так, чтобы достичь $\ge 43$: при 22–42 камнях Петя добавляет 1 или 2 камня и получает $\ge 43$. - Петя выигрывает за второй ход. Для $S = 20$: - Петя добавляет 1 камень → куча становится 21. - Ваня может: добавить 1 (→ 22), добавить 2 (→ 23) или удвоить (→ 42). - При любом ходе Вани куча содержит от 22 до 42 камней. - Петя добавляет камни и достигает $\ge 43$. - Петя выигрывает за второй ход. Проверим с помощью программы: ```python def f(x, h): if h == 4 and x >= 43: return 1 elif h == 4 and x < 43: return 0 elif x >= 43 and h < 4: 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)) result = [] for x in range(1, 43): if f(x, 1) == 1: result.append(x) print(result) ``` Функция `f(x, h)` возвращает 1, если текущий игрок выигрывает из позиции $x$ на ходу $h$. На нечётных ходах (Петя) ищется хотя бы один выигрывающий ход; на чётных ходах (Ваня) проверяется, что все его ходы приводят к выигрышу Пети. Программа выводит позиции, где Петя выигрывает за два хода: 19 и 20.

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