Решение: Стратегии в игре с кучами
Два игрока, Петя и Ваня, играют с двумя кучами камней. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в одной из куч в два раза. Игра завершается, когда суммарное количество камней становится не менее 61. Побеждает игрок, сделавший последний ход.
Для каждой указанной начальной позиции определите игрока, имеющего выигрышную стратегию, и опишите эту стратегию. Для позиции $(7, 25)$ постройте дерево всех партий, возможных при реализации указанной выигрышной стратегии. Дерево не должно содержать партии, невозможные при реализации стратегии выигрывающего игрока.
Решение по шагам
7 шаговРассмотрим позиции $(6, 27)$ и $(8, 26)$. Из позиции $(6, 27)$ возможны переходы в $(7, 27)$, $(12, 27)$, $(6, 28)$ и $(6, 54)$. В первых трёх позициях удвоение второй кучи приводит к сумме не менее 61, а из $(6, 54)$ соперник может сразу добавить один камень и завершить игру. Поэтому у игрока, который ходит из $(6, 27)$, нет безусловно выигрышного хода.
$$6+27=33$$Аналогично позиция $(8, 26)$ является проигрышной для игрока, делающего ход: любой его ход переводит игру в позицию, из которой следующий игрок может завершить игру или перейти к проигрышной для соперника позиции.
Следовательно, в начальных позициях $(6, 27)$ и $(8, 26)$ выигрышная стратегия есть у Вани. После хода Пети Ваня выбирает ход, переводящий игру в позицию, где Петя не может гарантированно выиграть; при необходимости Ваня сразу завершает игру.
В позиции $(6, 26)$ Петя добавляет один камень в первую кучу и получает $(7, 26)$. В позиции $(7, 26)$ Петя также добавляет один камень в первую кучу и получает $(8, 26)$. В позиции $(8, 25)$ Петя добавляет один камень во вторую кучу и получает $(8, 26)$. Поэтому во всех трёх позициях задания 2 выигрышная стратегия есть у Пети.
В позиции $(7, 25)$ возможны ходы Пети в $(8, 25)$, $(14, 25)$, $(7, 26)$ и $(7, 50)$. В первых трёх случаях Ваня может сделать выигрышный ход: из $(8, 25)$ перейти в $(8, 26)$, из $(14, 25)$ удвоить вторую кучу и получить $(14, 50)$, а из $(7, 26)$ добавить камень в первую кучу и получить $(8, 26)$. Из $(7, 50)$ Ваня удваивает первую кучу и сразу получает сумму не менее 61.
Таким образом, в позиции $(7, 25)$ выигрышная стратегия есть у Вани. После перехода в $(8, 26)$ любой ход Пети парируется ходом Вани, который либо сразу завершает игру, либо переводит игру в позицию с суммой не менее 61.
Дерево партий при стратегии Вани можно представить таблицей. В корне Петя выбирает любой из четырёх ходов, после чего Ваня действует по стратегии.
Задание 1: в позициях $(6, 27)$ и $(8, 26)$ выигрышная стратегия есть у Вани. Задание 2: в позициях $(6, 26)$, $(7, 26)$ и $(8, 25)$ выигрышная стратегия есть у Пети. Задание 3: в позиции $(7, 25)$ выигрышная стратегия есть у Вани.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать позицию с суммой 60 уже завершённой: игра завершается только при сумме не менее 61.
Включать в стратегию ходы, которые выигрывают только при неудачной игре соперника.
Строить полное дерево игры вместо дерева партий, совместимых с выигрышной стратегией Вани.
Забывать, что удвоение одной кучи изменяет только выбранную кучу.