Решение: Стратегия в игре с кучками
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при правильной игре — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение по шагам
6 шаговПосле первого хода первого игрока возможны четыре позиции: $(4, 2)$, $(3, 3)$, $(9, 2)$ или $(3, 6)$.
Позиция $(4, 3)$ проигрышна для игрока, которому предстоит ходить. Действительно, из неё нельзя сразу получить сумму не менее 16. После добавления камня получаются позиции $(5, 3)$ или $(4, 4)$, после утроения — $(12, 3)$ или $(4, 9)$. В каждой из этих позиций следующий игрок может выиграть: утроить кучку из 5 или 4 камней, добавить камень к $(12, 3)$ или утроить кучку из 9 камней.
Если первый игрок сделал ход $(3, 2) \to (4, 2)$, второй добавляет камень во вторую кучку и получает $(4, 3)$.
Если первый игрок сделал ход $(3, 2) \to (3, 3)$, второй добавляет камень в любую кучку и получает $(4, 3)$.
Если первый игрок утроил первую кучку и получил $(9, 2)$, второй утроением первой кучки получает сумму $27+2=29$, то есть выигрывает.
Если первый игрок утроил вторую кучку и получил $(3, 6)$, второй утроением второй кучки получает сумму $3+18=21$, то есть выигрывает.
При правильной игре выигрывает второй игрок. Если первый игрок добавляет камень, второй добавляет камень в другую кучку и получает позицию $(4, 3)$. Если первый игрок утроит одну из кучек, второй утроит ту же кучку и сразу выиграет.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Считать выигрышным первый ход, который просто увеличивает общую сумму.
Не рассмотреть отдельно четыре возможных первых хода.
Забыть, что утроение кучки из 6, 9 или 12 камней сразу приводит к сумме не менее 16.