Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 56. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 56 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 55. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Укажите такое S, при котором Петя не выигрывает своим первым ходом
Чтобы определить, при каком начальном количестве камней \( S \), Петя не сможет выиграть при своем первом ходе, необходимо рассмотреть стратегию игры и понять, какие позиции являются выигрышными, а какие — проигрышными.
Мы будем рассматривать количество камней в куче \( n \) от 1 до 55. Игрок, который сделает ход из положения, где количество камней достигает 56 или более, выигрывает. Если игрок находится в позиции, откуда любой возможный ход приведет к выигрышной позиции соперника, то эта позиция является проигрышной.
Давайте проанализируем позиции:
- Позиция 56 (выигрышная): Игрок, который получает 56 или больше, выигрывает.
- Позиция 55 (проигрышная): Если у игрока 55 камней, любые его ходы (добавление 1, добавление 2 или удвоение) приведут к выигрышной позиции 56, 57 или 110, соответственно.
- Позиция 54 (выигрышная): Игрок может добавить 2 камня, чтобы получить 56.
- Позиция 53 (выигрышная): Игрок может добавить 1 камень, чтобы получить 54.
- Позиция 52 (проигрышная): Если игрок добавляет 1 или 2 камня, он попадет в позицию 53 или 54, а если удваивает, то окажется в 104.
- Позиция 51 (выигрышная): Игрок может добавить 1 камень, чтобы получить 52.
- Позиция 50 (выигрышная): Игрок может добавлять 2 камня, чтобы получить 52.
- Позиция 49 (проигрышная): Из 49 камней любой ход приведет к выигрышной позиции соперника.
Продолжая этот процесс, можно заметить, что проигрышные позиции чередуются:
- Проигрышные: 55, 52, 49, 46, 43, 40, 37, 34, 31, 28, 25, 22, 19, 16, 13, 10, 7, 4, 1.
Таким образом, начиная с 1, 4, 7, 10 и т.д., для любого игрока, начиная с этих чисел, будет проигрышная позиция.
Теперь проверим, при каком начальном количестве камней \( S \) Петя, начиная первым, не имеет выигрышной стратегии. Минимальное такое количество камней — \( S = 55 \). В этой позиции Петя не сможет выиграть, так как любой его ход приведет к выигрышной позиции Вани.
Итак, Петя не выиграет своим первым ходом, если в начале игры в куче было 55 камней.
