Решение: Стратегии в игре с камнями
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень либо увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 26. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 26 или больше камней. В начальный момент в куче было $S$ камней, $1 \leq S \leq 25$.
Игрок имеет выигрышную стратегию, если может выиграть при любых ходах противника. В описание выигрышной стратегии не следует включать ходы, не являющиеся безусловно выигрышными.
Выполните следующие задания. Во всех случаях обоснуйте ответ.
Задание 1а. Укажите все значения $S$, при которых Петя может выиграть за один ход.
Задание 1б. Укажите значение $S$, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2. Укажите два значения $S$, при которых у Пети есть выигрышная стратегия, Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от хода Вани. Для каждого значения опишите выигрышную стратегию Пети.
Задание 3. Укажите значение $S$, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, позволяющей гарантированно выиграть первым ходом. Для указанного значения опишите стратегию Вани и постройте дерево всех партий, возможных при этой стратегии.
Решение по шагам
5 шаговЗа один ход из позиции $S$ можно получить $S+1$ или $2S$. Петя выигрывает первым ходом, если один из результатов не меньше 26.
$$$S+1 \geq 26$ или $2S \geq 26$$$Условие $S+1 \geq 26$ даёт $S=25$, а условие $2S \geq 26$ даёт $S \geq 13$. Поэтому все значения: $13,14,\ldots,25$.
Для задания 1б нужно, чтобы оба хода Пети приводили в позиции, из которых Ваня выигрывает одним ходом. Подходит $S=12$: после хода $+1$ получается 13, после удвоения — 24. Из 13 Ваня удваивает кучу и получает 26, а из 24 добавляет один камень и получает 25? Нет, поэтому для позиции 24 Ваня должен удвоить кучу и получить 48. В обоих случаях Ваня выигрывает первым ходом.
Для задания 2 Петя должен первым ходом получить позицию, из которой после любого хода Вани Петя завершает игру следующим ходом. Из позиции 7 Ваня может получить 8 или 14; из обеих позиций Петя выигрывает следующим ходом. Петя получает 7 из 6 ходом $+1$. Из позиции 11 Ваня может получить 12 или 22; из обеих позиций Петя выигрывает следующим ходом. Петя получает 11 из 10 ходом $+1$.
Проверим задание 3. При $S=1,2,3,4,5$ Петя может сделать ход в 2–6 соответственно, и Ваня не может гарантированно завершить игру первым или вторым ходом: после ответных ходов остаются позиции, из которых Петя может продолжить игру. При $S=6$ Петя имеет выигрышную стратегию из задания 2. При $S \geq 7$ Петя может выиграть первым ходом или значение уже не соответствует условиям заданий. Следовательно, значения $S$, удовлетворяющего всем условиям задания 3, не существует.
1а: $S=13,14,\ldots,25$; 1б: $S=12$; 2: $S=6$ и $S=10$; 3: подходящего значения $S$ не существует, поэтому построение требуемого дерева невозможно.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать, что из позиции 24 Ваня должен добавить один камень; на самом деле он удваивает количество камней и сразу получает 48.
Забывать, что игра заканчивается сразу после получения 26 или большего количества камней.
В задании 2 рассматривать только один ход Вани вместо проверки обоих возможных ходов.
Пытаться подобрать значение для задания 3, не проверив, что при $S=6$ Петя уже имеет собственную стратегию выигрыша за второй ход.