5. Два игрока играют в следующую игру. Перед ними лежат две кучи камней, в первой из которых 1 камень, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Ответ
Для определения стратегии выигрыша в данной игре рассмотрим возможные состояния игры, начиная с начального состояния:
- (1, 2) — начальное состояние
Первый игрок может увеличить количество камней во второй куче до 4, добавив 2 камня. Тогда состояние станет (1, 4).
Теперь рассмотрим возможные ходы, которые сделает второй игрок:
- Второй игрок увеличивает количество камней во второй куче до 8 (1, 8). Тогда первый игрок увеличивает количество камней во второй куче до 24 (1, 24).
- Второй игрок увеличивает количество камней во второй куче до 5 (1, 5). Тогда первый игрок добавляет 2 камня во вторую кучу и получает (1, 7). После чего второй игрок может увеличить количество камней во второй куче до 21 (1, 21).
Таким образом, независимо от хода, который сделает второй игрок, первый игрок может обеспечить окончательное состояние (1, 24) или (1, 21), в котором общее количество камней становится не менее 17.
Исходя из этого, выигрывающим является первый игрок, делающий первый ход. Он должен увеличить количество камней во второй куче до 4, добавив 2 камня.