Решение: Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в три раза. Игра заканчивается, как только суммарное количество камней в кучах становится не менее 74. Побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, во второй — $S$ камней, где $1 \leq S \leq 67$.
Опишите выигрышные стратегии и постройте дерево партий, возможных при выигрышной стратегии Вани.
Решение по шагам
5 шаговИз начальной позиции $(6,S)$ Петя может выиграть за один ход утроением второй кучи, если $6+3S\geq74$. Отсюда $S\geq23$. При меньших значениях утроение первой кучи и добавление одного камня также не дают выигрыша.
$$6+3S\geq74\Longleftrightarrow S\geq\frac{68}{3}\Longleftrightarrow S\geq23$$Следовательно, в задании 1а подходят все значения $S$ от 23 до 67.
Для пункта 1б рассмотрим неудачный ход Пети — утроение второй кучи. При $S=8$ получается позиция $(6,24)$. Ваня утроением второй кучи получает $(6,72)$ и затем выигрывает добавлением двух камней? Точнее, Ваня сразу утроивает первую кучу и получает $(18,24)$, после чего сумма равна 42; выигрышным является утроение второй кучи до $(6,72)$, после чего следующий ход уже не требуется, поскольку в данной позиции сумма меньше 74. Поэтому минимальный случай определяется проверкой всех ходов и равен $S=8$.
При $S=8$ Петя не может выиграть сразу, но ходом $(6,8)\to(6,24)$ создаёт позицию, после которой любой ход Вани позволяет Пете получить сумму не менее 74: из $(7,24)$ утроением второй кучи, из $(18,24)$ утроением второй кучи, из $(6,25)$ утроением второй кучи, а после $(6,72)$ игра уже заканчивается.
Для задания 3 подходит $S=18$. Ваня после первого хода Пети выбирает ход, переводящий игру в позицию, из которой он гарантированно выигрывает первым или вторым ходом. Стратегия Вани строится разбором четырёх возможных первых ходов Пети.
1а) $S=23,24,25,\ldots,67$; 1б) $S=8$; 2) $S=8$, Петя утроивает вторую кучу; 3) $S=18$, Ваня использует стратегию ответа на каждый первый ход Пети.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать выигрышем позицию, в которой сумма камней ещё меньше 74.
Рассматривать только добавление одного камня и забывать об утроении кучи.
Включать в стратегию ходы, которые не гарантируют победу независимо от ответа соперника.
Строить полное дерево игры вместо дерева партий, совместимых с выигрышной стратегией.