Question

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

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

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

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

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

Accepted Answer

14

Answer

Идея решения: построить рекурсивную функцию, которая определяет, может ли текущий игрок выиграть за не более чем заданное количество своих ходов, и найти начальные позиции, где Ваня (второй игрок) выигрывает за два хода, но не за один. Обозначим через $h$ номер хода (начиная с 1 для первого хода Пети). Функция возвращает 1, если игрок, чей ход сейчас, может выиграть; 0 иначе. Для позиции $(x, h)$: - Если $h$ нечётно (ход Пети), он выигрывает, если существует хотя бы один ход, ведущий в выигрышную позицию. - Если $h$ чётно (ход Вани), он выигрывает, если существует хотя бы один ход, ведущий в выигрышную позицию. - Если $x \ge 40$ и это ход игрока, который только что достиг этого значения, то предыдущий игрок выиграл. Сначала найдём все позиции, где Ваня выигрывает за два хода (то есть на ходе 5 — после двух ходов Пети и двух ходов Вани): ```python def f(x, h): if (h == 3 or h == 5) and x >= 40: return 1 elif h == 5 and x < 40: return 0 elif x >= 40 and h < 5: return 0 else: if h % 2 == 1: # ход Пети (нечётный номер) 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) or f(x + 4, h + 1) or f(x * 2, h + 1)) def f1(x, h): if h == 3 and x >= 40: return 1 elif h == 3 and x < 40: return 0 elif x >= 40 and h < 3: return 0 else: if h % 2 == 1: # ход Пети 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)) # Позиции, где Ваня выигрывает за два хода positions_two = [] for x in range(1, 40): if f(x, 1) == 1: positions_two.append(x) # Позиции, где Ваня выигрывает за один ход positions_one = [] for x in range(1, 40): if f1(x, 1) == 1: positions_one.append(x) # Исключаем позиции, где Ваня выигрывает за один ход result = [x for x in positions_two if x not in positions_one] print(min(result)) ``` Логика: функция `f` проверяет выигрыш за два хода Вани (до хода 5), функция `f1` проверяет выигрыш за один ход Вани (до хода 3). Нам нужны позиции, которые есть в первом списке, но отсутствуют во втором.

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