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