Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу
Игра завершается в тот момент, когда количество камней в куче становится
В начальный момент в куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Известно, что Петя не может выиграть своим первым ходом, однако после любого хода Пети Ваня может выиграть. При каком
Сперва найдем, из каких позиций можно выиграть первым ходом (сразу). Это значения из диапазона [20; 39]. Увеличив кучу вдвое, игрок получает количество камней, достаточное для победы. Поэтому если игрок любым своим ходом приходит в одну из позиций выше, то он проигрывает. Такое
Ответ: 19.
Приведём другое решение на языке Python.
def f(x, h):
if h == 3 and x >= 40:
return 1
elif h == 3 and x < 40:
return 0
elif x >= 40 and h < 3:
return 0
else:
if h % 2 == 0:
return f(x + 1, h + 1) or f(x + 4, h + 1) or f(x * 2, h + 1) # стратегия победителя
else:
return f(x + 1, h + 1) and f(x + 4, h + 1) and f(x * 2, h + 1) # стратегия проигравшего(любой ход)
for x in range(1, 40):
if f(x, 1) == 1:
print(x)
break
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу
Игра завершается в тот момент, когда количество камней в куче становится
В начальный момент в куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Известно, что Петя имеет выигрышную стратегию в два хода, при этом Петя не может выиграть первым ходом. Укажите два
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу
Игра завершается в тот момент, когда количество камней в куче становится
В начальный момент в куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Известно, что Ваня имеет выигрышную стратегию за один или два хода, при этом не имеет выигрышной стратегии в один ход. Найдите минимальное значение S, при котором это возможно.