Задача №9 (Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию)
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает количество камней в меньшей кучке или добавляет 3 камня в большую кучку. Игрок, после хода которого общее число камней в двух кучках становится не менее 14, выигрывает. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Таблица 1.
Таблица 2.
Таблица 3.
Решение: Рассмотрим потенциальные ходы обоих игроков.
1 ход - первый игрок
| Начальная позиция | Ходы первого игрока |
| (3,2) | (3,4) |
| (6,2) |
2 ход - второй игрок
| Ходы первого игрока | Ходы второго игрока |
| (3,4) | (6,4) |
| (3,7) | |
| (6,2) | (9,2) |
| (6,4) |
3 ход - первый игрок
Повторяющиеся ходы второго игрока не рассматриваем.
| Ходы второго игрока | Ходы первого игрока |
| (6,4) | (6,8) |
| (9,4) | |
| (3,7) | (6,7) |
| (3,10) | |
| (9,2) | (9,4) |
| (12,2) |
Выделенные ходы являются выигрышем первого игрока. Соответственно ходы: (6,4) и (9,2) являются проигрышными для второго игрока. Он будет вынужден их совершить, если первый игрок на первом ходу пойдёт (6,2). Ответом на первый вопрос будет - при безошибочной игре выигрывает игрок, делающий первый ход. На третьем ходу первый игрок выигрывает.
Ответом на второй вопрос будет - первый ход выигрывающего игрока (6,2), так как именно этот ход приводит к проигрышным ходам для второго игрока на втором ходу.