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