Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в шесть раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 60 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче превышает 365. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 366 или больше камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 365. Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Найдите минимальное значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Давайте разберем эту задачу шаг за шагом, чтобы понять, какие условия должны быть выполнены, чтобы Ваня мог выиграть, если он будет следовать определённой стратегии.
Понимание игры
Ходы игроков:
- Игроки могут либо добавить 1 камень, либо увеличить количество камней в 6 раз.
- Игра заканчивается, когда количество камней превышает 365.
- Победителем считается тот, кто последний сделал ход.
Цель задачи:
- Найти минимальное значение \( S \) (начальное количество камней), при котором у Вани стратегически выигрышная позиция, если он делает ход первым или вторым, но при этом он не может гарантированно выиграть, если ходит первым.
Анализ выигрышной и проигрышной позиции
Чтобы найти стратегию, давайте разберем, какие позиции являются выигрышными, а какие проигрышными.
- Выигрышная позиция: Игрок, который находится в этой позиции, может действовать таким образом, чтобы привести противника в проигрышную позицию в следующем ходе.
- Проигрышная позиция: Игрок, который находится в этой позиции, не может избежать наступления на выигрышную позицию для противника в следующем ходе.
Определение позиций
Если количество камней достигает или превышает 366:
- Игрок, который делает последний ход, выигрывает.
- Например, если находимся в \( S = 366 \), то последний ход произошел, и игрок выиграл.
Проигрышные позиции:
- Рассмотрим малые значения \( S \):
- \( S = 365 \) → игрок сделает последний ход, добавляя 1 и выиграет.
- \( S = 364 \) → игрок добавляет 1, потом противник выигрывает следующим ходом.
- \( S = 363 \) → игрок добавляет 1 (364), противник добавляет 1 и выигрывает (365).
- \( S = 362 \) → игрок добавляет 1 (363), игрок противника может снова выиграть, и так далее.
- Рассмотрим малые значения \( S \):
Остальные позиции подбираются аналогично.
- В роли проигрышных позиций находятся числа 365 (выигрыш) и те, при добавлении 1 или умножении на 6, приводят к выигрышному числу.
Выравнивание условий победы
Чтобы найти подходящее значение \( S \):
- Ваня должен иметь выигрышную стратегию, то есть он должен иметь возможность всегда перевести Петю в проигрышную позицию, когда С ≤ 365.
- Ваня не может иметь выигрышную стратегию в начале игры.
Давайте проверим несколько значений:
- При \( S = 1 \) до \( S = 6 \) Ваня имеет выигрышную стратегию.
- При \( S = 7 \) Ваня может вывести в проигрышную позицию, добавив 1 в каждый свой ход.
Однако, при \( S = 30 \) и меньших значениях – с каждой трансформацией кучи позиция меняется.
Вывод решения
Глубокий анализ показывает, что минимальное значение \( S \):
- Каждая последовательность до 365 с определёнными шагами приводит к числам, при которых Петя будет иметь выигрышные позиции.
Ближайшее значение, где это нарушается, для начального \( S \), которое подходит под оба условия и участвует в проигрышной стратегии за Ваню, составляет:
\[ S = 30 \]
Таким образом, минимальное значение \( S \), которое удовлетворяет обоим условиям, — это 30.
