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