Question

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

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

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

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

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

Accepted Answer

1518

Answer

Идея решения: найти позиции, из которых первый игрок выигрывает за один ход, затем определить позиции, из которых первый игрок не выигрывает за один ход, но гарантирует выигрыш за два хода.

**Шаг 1. Позиции выигрыша за один ход.**

Первый игрок выигрывает за один ход, если может достичь значения $\ge 40$ одним ходом. Из позиции $S$ доступны ходы: $S + 1$, $S + 4$, $2S$.

Для $S \in [20, 39]$: удвоение даёт $2S \in [40, 78]$, что приводит к победе.

Для $S < 20$: ни один ход не достигает 40.

Таким образом, множество позиций выигрыша за один ход: $A = \{20, 21, \ldots, 39\}$.

**Шаг 2. Позиции выигрыша за два хода.**

Первый игрок выигрывает за два хода, если:
- Он не выигрывает за один ход (то есть $S 
otin A$, значит $S < 20$).
- После его хода второй игрок попадает в позицию, из которой любой его ход приводит первого в позицию выигрыша за один ход.

Иными словами, нужно найти позицию $T$, такую что все ходы из $T$ ведут в множество $A$.

Из позиции $T$ доступны ходы: $T + 1$, $T + 4$, $2T$.

Требуется: $T + 1 \in A$, $T + 4 \in A$, $2T \in A$.

Это означает: $T + 1 \ge 20$, $T + 4 \ge 20$, $2T \ge 20$ и все три значения $\le 39$.

Из $T + 1 \ge 20$ получаем $T \ge 19$.
Из $2T \le 39$ получаем $T \le 19{,}5$, то есть $T \le 19$.

Следовательно, $T = 19$.

Проверка: из 19 доступны ходы $20, 23, 38$ — все в диапазоне $[20, 39]$. ✓

**Шаг 3. Позиции, из которых первый ход ведёт в позицию 19.**

Нужно найти $S < 20$ такие, что один из ходов $S + 1$, $S + 4$, $2S$ равен 19.

- $S + 1 = 19 \Rightarrow S = 18$.
- $S + 4 = 19 \Rightarrow S = 15$.
- $2S = 19 \Rightarrow S = 9{,}5$ (не целое).

Таким образом, $S \in \{15, 18\}$.

Проверка:
- Из 15: ходы $16, 19, 30$. Ход в 19 приводит ко второму игроку, из 19 все ходы в $[20, 39]$. ✓
- Из 18: ходы $19, 22, 36$. Ход в 19 приводит ко второму игроку, из 19 все ходы в $[20, 39]$. ✓

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