Question

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

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

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

Accepted Answer

34

Answer

Идея решения: используем рекурсивный анализ позиций с учётом хода игрока — на чётных ходах побеждает тот, кто может достичь ≥ 69, на нечётных нужно, чтобы все ходы противника вели в проигрышные позиции. Обозначим позицию как $(x, h)$, где $x$ — количество камней, $h$ — номер хода (1 для Пети, 2 для Вани и т. д.). Функция $f(x, h)$ возвращает 1, если текущий игрок выигрывает, и 0 иначе. Базовые случаи: - Если $h = 3$ (ход Пети на третьем уровне) и $x \ge 69$, то Ваня уже выиграл на ходе 2, возвращаем 1. - Если $h = 3$ и $x < 69$, то Ваня не выиграл, возвращаем 0. - Если $x \ge 69$ и $h < 3$, то предыдущий игрок выиграл, возвращаем 0. Рекурсивные случаи: - На ходе Пети ($h$ нечётное): он выигрывает, если хотя бы один из его ходов (добавить 1 или удвоить) ведёт в выигрышную позицию. - На ходе Вани ($h$ чётное): он выигрывает, если оба его хода ведут в выигрышные позиции (то есть при любом ходе Пети Ваня может ответить выигрышно). ```python def f(x, h): if h == 3 and x >= 69: return 1 elif h == 3 and x < 69: return 0 elif x >= 69 and h < 3: return 0 else: if h % 2 == 1: # ход Пети (нечётный номер) return f(x + 1, h + 1) or f(x * 2, h + 1) else: # ход Вани (чётный номер) return f(x + 1, h + 1) and f(x * 2, h + 1) for x in range(1, 69): if f(x, 1) == 1: print(x) break ``` Проверим несколько значений: - $S = 33$: Петя может получить 34 или 66. Из 34 Ваня получает 35 или 68, из 66 Ваня получает 67 или 132 (≥ 69, Ваня выигрывает). Петя не гарантирует выигрыш. - $S = 34$: Петя может получить 35 или 68. Из 35 Ваня получает 36 или 70 (≥ 69, Ваня выигрывает). Из 68 Ваня получает 69 (≥ 69, Ваня выигрывает). При любом ходе Пети Ваня выигрывает. - $S = 35$: Петя может получить 36 или 70 (≥ 69, Петя выигрывает за один ход). Таким образом, минимальное значение, при котором Петя не выигрывает за один ход, но Ваня выигрывает при любом ходе Пети, равно 34.

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