Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом не разрешается делать ход, после которого количество камней в куче будет делиться
Например, если в начале игры в куче 4 камня, Петя может первым ходом получить кучу
Игра завершается, когда количество камней в куче становится
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой
В начальный момент в куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое
Такое значение S — 74. Своим первым ходом Петя может получить
Ответ: 74.
Приведем решение Даниила Травинова на языке Python.
def game(pile, mov):
if mov == 3 and pile >= 151:
return 1
elif mov == 3 and pile < 151:
return 0
elif mov < 3 and pile >= 151:
return 0
else:
if mov % 2 == 0:
if (pile + 1) % 3 == 0:
return game(pile + 2, mov + 1) or game(pile * 2, mov + 1)
elif (pile + 2) % 3 == 0:
return game(pile + 1, mov + 1) or game(pile * 2, mov + 1)
elif (pile * 2) % 3 == 0:
return game(pile + 1, mov + 1) or game(pile + 2, mov + 1)
else:
if (pile + 1) % 3 == 0:
return game(pile + 2, mov + 1) and game(pile * 2, mov + 1)
elif (pile + 2) % 3 == 0:
return game(pile + 1, mov + 1) and game(pile * 2, mov + 1)
elif (pile * 2) % 3 == 0:
return game(pile + 1, mov + 1) and game(pile + 2, mov + 1)
for pile in range(1, 150):
if pile % 3 != 0:
if game(pile, 1) == 1:
print(pile)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом не разрешается делать ход, после которого количество камней в куче будет делиться
Например, если в начале игры в куче
Игра завершается, когда количество камней в куче становится
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой
В начальный момент в куче было
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите два значения S, при которых Петя не может выиграть первым ходом, но у Пети есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Вани.
В ответе запишите найденные значения в порядке возрастания: сначала меньшее, затем большее.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в два раза. При этом не разрешается делать ход, после которого количество камней в куче будет делиться
Например, если в начале игры в куче
Игра завершается, когда количество камней в куче становится
Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 151 или больше камней.
В начальный момент в куче было
Найдите такое значение S, при котором у Вани есть стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.