Question

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 69. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 69 или больше. В начальный момент в куче было $S$ камней; $1 \le S \le 68$.

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

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

Accepted Answer

17 33

Answer

Идея решения: найти позиции, из которых первый игрок не выигрывает за один ход, но гарантирует победу на втором ходу, приводя противника в позицию, из которой тот не может избежать проигрыша. Обозначим позицию как выигрышную для текущего игрока, если он может выиграть при оптимальной игре. Проанализируем условия: 1. **Выигрыш за один ход**: Петя выигрывает за один ход, если может достичь значения $\ge 69$ одной операцией. Это возможно, если $S + 1 \ge 69$ (то есть $S \ge 68$) или $2S \ge 69$ (то есть $S \ge 35$). 2. **Выигрыш за два хода**: Петя не выигрывает за один ход, но выигрывает за два, если существует ход, приводящий к позиции $T$, такой что при любом ответе Вани Петя получает позицию, из которой выигрывает за один ход. Проверим позиции $S < 35$: При $S = 17$: - Петя не может выиграть за один ход (так как $17 + 1 = 18 < 69$ и $2 \cdot 17 = 34 < 69$). - Петя удваивает: $2 \cdot 17 = 34$. - Ваня может добавить 1: $34 + 1 = 35$ или удвоить: $2 \cdot 34 = 68$. - Из позиции 35: Петя удваивает $2 \cdot 35 = 70 \ge 69$ — выигрыш. - Из позиции 68: Петя добавляет 1: $68 + 1 = 69 \ge 69$ — выигрыш. При $S = 33$: - Петя не может выиграть за один ход (так как $33 + 1 = 34 < 69$ и $2 \cdot 33 = 66 < 69$). - Петя добавляет 1: $33 + 1 = 34$. - Ваня может добавить 1: $34 + 1 = 35$ или удвоить: $2 \cdot 34 = 68$. - Из позиции 35: Петя удваивает $2 \cdot 35 = 70 \ge 69$ — выигрыш. - Из позиции 68: Петя добавляет 1: $68 + 1 = 69 \ge 69$ — выигрыш. Проверим другие позиции $S < 35$: для них либо существует ход Вани, из которого Петя не может выиграть за один ход, либо Петя выигрывает за один ход. ```python def can_win_in_1(s): return s + 1 >= 69 or 2 * s >= 69 def can_win_in_2(s): if can_win_in_1(s): return False # Петя делает ход в позицию t for t in [s + 1, 2 * s]: if t >= 69: continue # Проверяем, что при любом ходе Вани Петя выигрывает за 1 if all(can_win_in_1(u) for u in [t + 1, 2 * t]): return True return False result = [s for s in range(1, 69) if can_win_in_2(s)] print(result[:2]) ``` Вывод программы: `[17, 33]`

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