Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один…
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда количество камней в куче становится не менее 42. В начальный момент в куче было S камней; 1 \le S \le 41. В результате аналитического решения задачи 19 найдено значение выигрыша Вани первым ходом: 20. В результате решения задачи 20 найдено три значения выигрыша Пети вторым ходом: 10, 17, 19. Постройте дерево партий и найдите минимальное значение S, при котором одновременно выполняются два условия: — у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; — у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Кратко: \(S_{\min}=16\). Условиям удовлетворяют \(S=16\) и \(S=18\), поэтому минимальное значение равно \(16\).
Ключевой факт
Если в куче \(n\ge21\), то игрок, чья очередь, сразу выигрывает: он удваивает количество камней, и \(2n\ge42\).
Если Ваня не может закончить игру сразу, то для победы своим вторым ходом ему выгодно оставить Пете ровно \(20\) камней. Тогда Петя может получить только \(21\), \(23\) или \(40\), после чего Ваня заканчивает игру. Если Ваня оставит \(19\) камней или меньше, Петя сможет сходить так, что Ваня не выиграет сразу. Если оставить от \(21\) до \(41\), Петя сам выиграет следующим ходом.
Дерево для \(S=16\)
Петя добавляет \(1\):
\[ 16 \to 17 \] Ваня добавляет \(3\): \[ 17 \to 20 \] Петя из \(20\) получает \(21\), \(23\) или \(40\). Ваня выигрывает: \[ 21\cdot2=42,\qquad 23\cdot2=46,\qquad 40+3=43. \]Петя добавляет \(3\):
\[ 16 \to 19 \] Ваня добавляет \(1\): \[ 19 \to 20 \] Далее всё так же, как в первом случае.Петя удваивает:
\[ 16 \to 32 \] Ваня сразу выигрывает: \[ 32\cdot2=64\ge42. \]
Значит, при \(S=16\) Ваня гарантированно побеждает своим первым или вторым ходом.
Но гарантии победы именно первым ходом у Вани нет: Петя может начать с \(16+1=17\). Из \(17\) Ваня может попасть только в \(18\), \(20\) или \(34\), а все эти числа меньше \(42\). Значит, сразу выиграть он не может.
Почему меньше \(16\) не подходит
Если \(S<16\) и Ваня вообще имеет выигрышную стратегию, то \(S\) должна быть проигрышной позицией для Пети. Для \(S<16\) такие позиции:
\[
1,\ 3,\ 5,\ 12,\ 14.
\]
В каждой из них Петя может сходить \(+1\): \[ 1\to2,\quad 3\to4,\quad 5\to6,\quad 12\to13,\quad 14\to15. \] Из позиций \(2,4,6,13,15\) Ваня не может ни выиграть сразу, ни попасть в \(20\). Поэтому он не может гарантировать победу своим вторым ходом. Значит, все \(S<16\) не подходят.
Ответ: \(S_{\min}=16\).
