Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу из 4, 5 или
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 34. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое
Такое значение S — 16. Своим первым ходом Петя может получить позиции 17, 18 и 32. В первых двух случаях Ваня удваивает количество камней в куче, в третьем случае Ваня добавляет в кучу два камня. Во всех случаях Ваня выигрывает своим первым ходом.
Ответ: 16.
Приведём другое решение на языке Python.
Для контроля ходов игроков заведём переменную m.
Если m = 1, то это действие x + 1
Если m = 2, то это действие x + 2
Если m = 3, то это действие x * 2
Таким образом, можно исключать ходы, которые уже были сделаны, не включая их в возвращаемые значения функции.
def f(x, h, m):
if h == 3 and x >= 34:
return 1
elif h == 3 and x < 34:
return 0
elif x >= 34 and h < 3:
return 0
else:
if h % 2 == 0:
if h == 2:
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, 1) and f(x + 2, h + 1, 2) and f(x * 2, h + 1, 3)
for x in range(1, 34):
if f(x, 1, 0) == 1:
print("Задача 19:", x)
break
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче 3 камня, Петя может первым ходом получить кучу
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Существует несколько таких
В ответе запишите сначала наименьшее, затем наибольшее значение.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Найдите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.