Для игры, описанной в задании 19, найдите минимальное...

Задание:

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

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

Если найдено несколько значений S, в ответе запишите минимальное из них.

Решение (аналитическое)

Начнем рассуждение с построения дерева гипотетической игры.

В дереве ходы, обозначенные h1 , h_mx/h_mn, покрывают все возможные ходы для S+1 и 2∙S. При этом до проведения дальнейшего анализа мы не можем сказать, к какой игре будет сведена дальнейшая игра, потому что по условию возможен как вариант, где игра будет длиной ровно в 4 хода, как и вариант, где после одного допустимого хода игра завершится на 4 ходе, после другого допустимого хода – на 2 ходе.

Таким образом, можно заключить, что после первого хода Петя должен прийти в позицию, которая соответствует одному из значений S ∈ {32, 63,65 … 129}.

При этом не должно быть стратегии для игры в два хода. Или S ≠ 64

Исследуем значения S из которых можно прийти в указанные действием увеличения на 1. Таких значений 2: 31 и 62.

Из 31 первый игрок может попасть в 32 и 62 (значение 62 отсутствует в множестве значений для следующей позиции).
Из 62 в 63 и 124 (оба значения входят в необходимое множество).

Следовательно, ответ 62.
Дерево игры для этого значения выглядит следующим образом:

Ответ: 62

Решение (программное, на списке)

# определяем список для пометки позиций
steps = [0]*129
for S in range(129):
   # Если можно сделать 129 или больше камней одним ходом
   if S + 1 >= 129 or S*2 >= 129:
     # помечаем позицию, как позицию для игры в 1 ход
     steps[S] = 1

for S in range(129):
   # если позиция еще не помечена
   # и все ходы ведут в позицию для игры в 1 ход
   if steps[S] == 0 and steps[S+1]==1 and steps[S*2] == 1:
     # помечаем позицию, как позицию для игры в 2 хода
     steps[S] = 2

# выводим минимальное значение S для игры в 2 хода
print('19.', min(S for S in range(129) if steps[S] == 2))

for S in range(129):
 # если позиция еще не помечена
 # и хотя бы один из ходов ведет
 # в позицию для игры в 2 хода
 if steps[S] == 0 and (steps[S+1]==2 or steps[S*2] == 2):
   # помечаем позицию, как позицию для игры в 3 хода
   steps[S] = 3  

# выводим 2 минимальных значения S для игры в 3 хода
print('20.', *[S for S in range(129) if steps[S] == 3][:2])

for S in range(129):
 # если позиция еще не помечена
 # и все ходы ведут в позицию для игры в 1 или 3 хода
 if steps[S] == 0 and {steps[S+1], steps[S*2]} <= {1, 3}:
   # помечаем позицию, как позицию для игры в 4 хода
   steps[S] = 4

# выводим минимальное значение S для игры в 2 хода
print('21.', min(S for S in range(129) if steps[S] == 4)) 

Вывод:
19. 64
20. 32 63
21. 62

Решение (программное, рекурсия для дерева игры)

# функция возвращает номер хода,
# на котором игра завершится при выигрышной стратегии
# 0 – если ходов больше, чем 4
def game(S):
   if S+1 >= 129 or S*2 >= 129:
     return 1 

   g1 = game(S+1)
   g2 = game(S*2)  

   if g1 == 1 and g2 == 1:
     return 2
   
   if g1 == 2 or g2 == 2:
     return 3
   
   if g1 in (1, 3) and g2 in (1, 3):
     return 4
   
   return 0 

# 0 Не перебираем, так как 0*2 = 0
steps = [0] + [game(S) for S in range(1, 129)]
print('19.', min(S for S in range(129) if steps[S] == 2))
print('20.', *[S for S in range(129) if steps[S] == 3])
print('21.', min(S for S in range(129) if steps[S] == 4)) 

Вывод:
19. 64
20. 32 63
21. 62

Решение (программное, с контролем количества ходов)

Напишем рекурсивную функцию, которая будет работать следующим образом. Если игра оканчивается за n шагов или на четное количество шагов меньше, чем передано в параметре, возвращается True, иначе возвращается False.

Например, если нужно узнать окончится ли игра не позже, чем на 3 ходу Пети, то выход функции будет осуществляться, как game(S, 5). Так же это можно интерпретировать, как игра заканчивается не более, чем на 5 ходе победой Пети. То есть, если игра окончится на 2 ходе Пети, функция так же вернет значение True.

def game(S, c):
  if S >= 129:
   return c %2 == 0

  # если ходы кончились, а выиграть не удалось
  if c == 0:
   return False

  if c % 2 == 1:
   return game(S+1, c-1) or game(S*2, c-1)
  else:
   return game(S+1, c-1) and game(S*2, c-1)
 
st = [[] for _ in range(5)]
for S in range(129):
 for step in range(1, 5):
  if game(S, step):
   st[step].append(S)
   break 

print('19.', min(st[2]))
print('20.', *st[3][:2])
print('21.', min(st[4])) 

Вывод:
19. 64
20. 32 63
21. 62

Источник: Информатика с Джобсом | ЕГЭ