Для игры, описанной в задании 19, найдите минимальное значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволила бы ему гарантированно выиграть первым ходом.
Приведём решение на языке Python.
def f(x,k,v):
if x <= 19:
return k in v
if k >= max(v):
return 0
h = [f(x-1,k+1,v)]
if x % 3 == 0:
h.append(f(x//3,k+1,v))
else:
h.append(f(x-2,k+1,v))
if x % 5 == 0:
h.append(f(x//5,k+1,v))
else:
h.append(f(x-3,k+1,v))
if k%2 != max(v) % 2:
return any(h)
else:
return all(h)
for x in range (10,1000):
if f(x,0,[2,4]) == 1 and f(x,0,[2]) == 0:
print('Задание 21:',x)
break
Ответ: 28.
Приведём решение Юрия Красильникова на языке Python.
def game(n,lim,s): # номер хода, лимит ходов, количество камней
player=2-n%2 # текущий игрок
rival=3-player # противник
if s <= 19: return rival # игра закончена
if n > lim: return 0 # превышен лимит ходов - победителя нет
pos=[s-1, s//3 if s%3==0 else s-2, s//5 if s%5==0 else s-3] # количество камней после хода игрока
res=[game(n+1,lim,p) for p in pos] # результаты ходов
if all([r == rival for r in res]): return rival # все ходы проигрышные
if any([r == player for r in res]): return player # есть выигрышный ход
return 0 # победителя нет
print('#19:',*[s for s in range(20,100) if game(1,2,s) == 2])
print('#20:',*[s for s in range(20,100) if game(1,2,s) == 0 and game(1,3,s) == 1])
print('#21:',*[s for s in range(20,100) if game(1,3,s) == 0 and game(1,4,s) == 2 and game(1,4,s) == 2])
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может выполнить любое из следующих трёх действий:
1) убрать из кучи один камень;
2) если количество камней в куче кратно трём, уменьшить его в три раза, в противном случае убрать из кучи два камня;
3) если количество камней в куче кратно пяти, уменьшить его в пять раз, в противном случае убрать из кучи три камня.
Например, если в куче 12 камней, то за один ход можно получить 11, 4 или 9 камней.
Игра завершается, когда количество камней в куче становится не более 19.
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 19 или меньше камней.
В начале игры в куче было S камней, 
Укажите минимальное значение S, при котором Петя не может выиграть первым ходом, но при любом первом ходе Пети Ваня может выиграть своим первым ходом.
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани. В ответе запишите найденные значения в порядке возрастания.