Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
Такое значение S — 11. При S = 11 Петя своим первым ходом может получить одну из трёх позиций:
В ситуации, когда после первого хода Пети в куче становится
Ответ: 11.
Примечание.
Обращаем внимание тех читателей, у которых получается
Приведем решение Юрия Красильникова на языке Python.
def move(n,lim,s,t):
player = 2-n%2
rival = 3-player
if s >= 50: return rival
if n > lim: return 0
pos = [(s+1,0),(s+2,1),(s*2,2)]
if len(t) > 0: del pos[t[-1]]
res = [move(n+1,lim,x[0],t+[x[1]]) for x in pos]
if any([x==player for x in res]): return player
if all([x==rival for x in res]): return rival
return 0
print('#19:',*[s for s in range(1,50) if move(1,2,s,[])==2])
print('#20:',*[s for s in range(1,50) if move(1,1,s,[])==0 and move(1,3,s,[])==1])
print('#21:',*[s for s in range(1,50) if move(1,2,s,[])==0 and move(1,4,s,[])==2])
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Существует несколько таких
В ответе запишите сначала наименьшее, затем наибольшее значение.