Решение: Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют в игру с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной куче в три раза. Игра заканчивается, когда суммарное количество камней становится не менее 68. Побеждает игрок, сделавший последний ход. В начальный момент в первой куче было 6 камней, во второй — $S$ камней, где $1 \leq S \leq 61$.
Дайте развёрнутый ответ: решите три задания, укажите значения $S$, опишите выигрышные стратегии и постройте дерево партий для стратегии Вани.
Решение по шагам
8 шаговИз начальной позиции $(6,S)$ Петя может выиграть одним ходом, если после добавления камня или утраивания одной из куч сумма станет не менее 68.
Добавление одного камня в любую кучу даёт условие $7+S\geq68$, то есть $S\geq61$. Утраивание первой кучи даёт $18+S\geq68$, то есть $S\geq50$. Утраивание второй кучи даёт $6+3S\geq68$, то есть $S\geq21$.
Следовательно, в задании 1а подходят все значения $S$ от 21 до 61 включительно.
Для задания 1б берём минимальное значение $S$, при котором Петя может сделать неудачный ход, а Ваня затем выиграть сразу. При $S=7$ Петя может получить позицию $(6,21)$, утраив вторую кучу. После этого Ваня утраивает вторую кучу и получает $(6,63)$, где сумма равна 69.
Для задания 2 берём $S=13$. Петя не может выиграть первым ходом, поскольку $6+3\cdot13=45<68$. Он утраивает первую кучу и получает позицию $(18,13)$.
Из позиции $(18,13)$ Ваня не может выиграть сразу. После любого его хода Петя выигрывает следующим ходом: после увеличения первой кучи Петя утраивает первую; после увеличения второй кучи Петя также утраивает первую; после утраивания первой кучи Петя добавляет один камень в любую кучу; после утраивания второй кучи Петя утраивает первую.
Для задания 3 подходит $S=14$. Петя не может выиграть первым ходом. Ваня использует стратегию, зависящую от первого хода Пети: после хода, который оставляет возможность немедленной победы, Ваня выполняет утроение подходящей кучи; в остальных случаях Ваня переводит игру в позицию, из которой любой следующий ход Пети позволяет Ване завершить игру.
Основные ветви дерева стратегии Вани при $S=14$: $(6,14)\to(7,14)\to(21,14)$; $(6,14)\to(18,14)\to(54,14)$; $(6,14)\to(6,15)\to(18,15)$; $(6,14)\to(6,42)\to(6,126)$. На каждой последующей ветви Ваня после хода Пети выбирает увеличение или утроение той кучи, которое первым даёт сумму не менее 68.
1а) $S=21,22,\ldots,61$. 1б) $S=7$. 2) $S=13$: Петя сначала утраивает первую кучу, получая $(18,13)$, после чего выигрывает вторым ходом при любом ходе Вани. 3) $S=14$: Ваня имеет стратегию выигрыша первым или вторым ходом, но не может гарантированно выиграть первым ходом.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Проверяют только утроение второй кучи и забывают про утроение первой.
Считают выигрышной любую позицию с суммой меньше 68, не анализируя все возможные ходы соперника.
В дерево стратегии включают все возможные партии, в том числе те, которые не возникают при правильной игре Вани.
Путают выигрыш за один ход с выигрышем вторым ходом.