Question

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было $S$ камней; $1 \leq S \leq 47$.

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

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

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

Accepted Answer

2022

Answer

Идея решения: найти позиции, из которых первый игрок не выигрывает за один ход, но гарантированно выигрывает за два, используя рекурсивный анализ игровых позиций с учётом чётности хода. Обозначим позицию как выигрышную для текущего игрока, если он может гарантировать победу при оптимальной игре противника. Используем рекурсивную функцию, которая анализирует позицию в зависимости от номера хода: - На ходу 4 (четвёртый ход Пети): если куча $\geq 48$, позиция выигрышная для Пети. - На нечётных ходах (ходы Пети): позиция выигрышная, если существует хотя бы один ход, приводящий к выигрышной позиции. - На чётных ходах (ходы Вани): позиция выигрышная для Пети, если все возможные ходы Вани приводят к выигрышным для Пети позициям. Проверяем все начальные значения $S$ от 1 до 47 и выбираем те, для которых: 1. Первый ход не приводит к куче $\geq 48$ (Петя не выигрывает за один ход). 2. Функция возвращает 1 (Петя выигрывает за два хода). ```python def f(x, h): if h == 4 and x >= 48: return 1 elif h == 4 and x < 48: return 0 elif x >= 48 and h < 4: return 0 else: if h % 2 == 0: return (f(x + 1, h + 1) and f(x + 3, h + 1) and f(x * 2, h + 1)) else: return (f(x + 1, h + 1) or f(x + 3, h + 1) or f(x * 2, h + 1)) for x in range(1, 48): if f(x, 1) == 1: print(x) ``` При $S = 20$: Петя добавляет 3 камня, получая 23. Ваня может получить 24, 26 или 46 камней. Во всех случаях Петя удваивает кучу и достигает минимум 48 камней, выигрывая вторым ходом. При $S = 22$: Петя добавляет 1 камень, получая 23. Ваня снова может получить 24, 26 или 46 камней. Петя удваивает и выигрывает.

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