Задача #4371

Задания 19–21

Уровень ЕГЭ

Общее условие для 19–21

(А. Шуруха) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу 5 камней либо увеличить количество камней в куче в 3 раза.
Например, из кучи в 20 камней за один ход можно получить кучу из 25 или 60 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее чем в четыре раза больше первоначального. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой камней не менее 4S, где S — количество камней в начальный момент. В начальный момент в куче было S камней; 1 ≤ S ≤ 150. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Вопрос для задания 21

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

Задание 19 Задание 20

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

Общий разбор связки

def moves(s):
  return [s + 5, 3 * s]
def f(s, m, lim):
  if s >= lim: return m % 2 == 0
  if m == 0: return False
  h = [f(x, m - 1, lim) for x in moves(s)]
  return any(h) if m % 2 else all(h)

a19 = [s for s in range(1, 151) if f(s, 2, 4 * s)]
a20 = [s for s in range(1, 151) if f(s, 3, 4 * s) and not f(s, 1, 4 * s)]
a21 = [s for s in range(1, 151) if f(s, 4, 4 * s) and not f(s, 2, 4 * s)]
print('19', len(a19))
print('20', min(a20), max(a20))
print('21', min(a21))

Решение для задания 21

Номер