Тип 20 № 46978 
Выигрышная стратегия. Задание 2. Одна куча
i
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается.
Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или 6 камней. Если Петя получил кучу из 5 камней (добавил два камня), то следующим ходом Ваня может получить 6, 7 или 10 камней. Если Ваня добавил один камень и получил 6 камней, то вторым ходом Петя может получить 7 или 12 камней. Получить 8 камней Петя не может, так как для этого нужно добавить 2 камня, а Петя делал это на предыдущем ходу.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается, когда количество камней в куче становится не менее 21. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 21 или больше камней. В начальный момент в куче было S камней, 1 ⩽ S ⩽ 20.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
В ответе запишите найденные значения в порядке возрастания: сначала меньшее, затем большее.
Решение. Рассмотрим значение S = 6. Своим первым ходом Петя может получить позиции 7, 8 и 12. В позиции 12 Ваня своим первым ходом удваивает количество камней в куче и выигрывает своим первым ходом. Из позиции 7 Ваня своим первым ходом может получить позицию 9, после чего Петя своим вторым ходом может получить позиции 11 и 18 (позицию 10 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. Из позиции 8 Ваня может получить позицию 10, после чего Петя своим вторым ходом может получить позиции 11 и 20 (позицию 12 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом.
Второе значение S — 7. Своим первым ходом Петя может получить позиции 8, 9 и 14. В позиции 14 Ваня своим первым ходом удваивает количество камней в куче и выигрывает своим первым ходом. Из позиции 8 Ваня своим первым ходом может получить позицию 9, после чего Петя своим вторым ходом может получить позиции 11 и 18 (позицию 10 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом. Из позиции 9 Ваня может получить позицию 10, после чего Петя своим вторым ходом может получить позиции 11 и 20 (позицию 12 Петя получить не может, поскольку игроку нельзя повторять свои предыдущие ходы). В обоих случаях Ваня своим вторым ходом удваивает количество камней в куче и выигрывает своим вторым ходом.
Ответ: 67.
Приведём другое решение на языке Python.
Заведём переменные, отслеживающие сделанные ходы.
Так можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.
Сначала найдём для победы Вани первым или вторым ходом, а затем исключим победу Вани только первым ходом.
def f(x, h, p, v):
if (h == 5 or h == 3) and x >= 21:
return 1
elif h == 5 and x < 21:
return 0
elif x >= 21 and h < 5:
return 0
else:
if h % 2 == 0:
if h == 2:
return f(x + 1, h + 1, p, 1) or f(x + 2, h + 1, p, 2) or f(x * 2, h + 1, p, 3) # стратегия победителя
elif h == 4:
if v == 1:
return f(x + 2, h + 1, p, v) or f(x * 2, h + 1, p, v)
elif v == 2:
return f(x + 1, h + 1, p, v) or f(x * 2, h + 1, p, v)
elif v == 3:
return f(x + 1, h + 1, p, v) or f(x + 2, h + 1, p, v)
else: # Петин ход
if h == 1:
return f(x + 1, h + 1, 1, v) and f(x + 2, h + 1, 2, v) and f(x * 2, h + 1, 3, v) # стратегия победителя
elif h == 3:
if p == 1:
return f(x + 2, h + 1, p, v) and f(x * 2, h + 1, p, v)
elif p == 2:
return f(x + 1, h + 1, p, v) and f(x * 2, h + 1, p, v)
elif p == 3:
return f(x + 1, h + 1, p, v) and f(x + 2, h + 1, p, v)
for x in range(1, 21):
if f(x, 1, 0, 0) == 1:
print("Задача 20:", x)
# Исключаем победу Вани только первым ходом
def f(x, h):
if h == 3 and x >= 21:
return 1
elif h == 3 and x < 21:
return 0
elif x >= 21 and h < 3:
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, 21):
if f(x, 1) == 1:
print("Победа Вани первым ходом:", x)
Приведем решение Юрия Красильникова на языке Python.
def move(n,lim,s,t):
player = 2-n%2
rival = 3-player
if s>= 21: return rival
if n > lim: return 0
pos = [(s+1,0),(s+2,1),(s*2,2)]
if len(t) > 1: del pos[t[-2]]
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,21) if move(1,1,s,[])==0 and move(1,3,s,[])==1])
print('#20:',*[s for s in range(1,21) if move(1,2,s,[])==0 and move(1,4,s,[])==2])
print('#21:',*[s for s in range(1,21) if move(1,3,s,[])==0 and move(1,5,s,[])==1])
PDF-версии: