Question

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

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

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

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

Accepted Answer

18

Answer

Идея решения: построить две функции анализа позиций — одну для проверки выигрыша Вани за два его хода (глубина 5 ходов), другую для проверки выигрыша за один его ход (глубина 3 хода), затем найти минимальное $S$, удовлетворяющее обоим условиям. Используем рекурсивный анализ с параметром глубины $h$ (номер хода). На чётных ходах (ход Пети) ищем выигрыш через дизъюнкцию (достаточно одного выигрышного хода), на нечётных (ход Вани) — через конъюнкцию (все ходы должны вести к выигрышу). Функция `f(x, h)` проверяет, может ли текущий игрок выиграть за два хода Вани (завершение на ходе 5): ```python def f(x, h): if (h == 3 or h == 5) and x >= 47: return 1 elif h == 5 and x < 47: return 0 elif x >= 47 and h < 5: return 0 else: if h % 2 == 0: return (f(x + 1, h + 1) or f(x + 4, h + 1) or f(x * 2, h + 1)) else: return (f(x + 1, h + 1) and f(x + 4, h + 1) and f(x * 2, h + 1)) ``` Функция `f1(x, h)` проверяет, может ли Ваня выиграть за один ход (завершение на ходе 3): ```python def f1(x, h): if h == 3 and x >= 47: return 1 elif h == 3 and x < 47: return 0 elif x >= 47 and h < 3: return 0 else: if h % 2 == 0: return (f1(x + 1, h + 1) or f1(x + 4, h + 1) or f1(x * 2, h + 1)) else: return (f1(x + 1, h + 1) and f1(x + 4, h + 1) and f1(x * 2, h + 1)) ``` Ищем позиции, где Ваня выигрывает за два хода, но не за один: ```python for x in range(1, 47): if f(x, 1) == 1 and f1(x, 1) == 0: print(x) break ``` Проверим логику для $S = 18$: - Петя может сделать ходы: $18 + 1 = 19$, $18 + 4 = 22$, $18 imes 2 = 36$. - Если получится 36, Ваня удвоит: $36 imes 2 = 72 \ge 47$ — Ваня выигрывает первым ходом. - Если получится 19, Ваня добавит 4: $19 + 4 = 23$. Петя может получить 24, 27 или 46. При любом ходе Ваня добавит камни и достигнет $\ge 47$. - Если получится 22, Ваня добавит 1: $22 + 1 = 23$. Аналогично предыдущему случаю. - Таким образом, Ваня гарантирует выигрыш за два своих хода. - Из начальной позиции 18 Ваня не может выиграть первым ходом (максимум $18 imes 2 = 36 < 47$).

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