Задача №7 (Умение построить дерево игры по заданному алгоритму и обосновать выигрышную стратегию)
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 1 камень. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в меньшей кучке или добавляет два камня в большую кучку. Выигрывает игрок, после хода которого общее число камней в двух кучках становится не менее 30. Кто выигрывает при безошибочной игре — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение: Рассмотрим потенциальные ходы обоих игроков.
1 ход - первый игрок
Таблица 1.
2 ход - второй игрок
Повторяющиеся ходы первого игрока не рассматриваем.
Таблица 2.
3 ход - первый игрок
Таблица 3.
Выделенные ходы являются выигрышем первого игрока. Соответственно ходы: (27,1), (9,3), (11,1), (15,1) являются проигрышными для второго игрока. По условию задачи - игра безошибочная второй игрок эти ходы не сделает. Но если на первом ходу первый игрок пойдёт (9,1), то у второго игрока на втором ходу не будет других вариантов, как пойти проигрышными ходами (27,1), (9,3) и (11,1). Соответственно, на третьем ходу выиграет первый игрок. Ответом на первый вопрос будет - при безошибочной игре выигрывает игрок, делающий первый ход. На третьем ходу первый игрок выигрывает.
Ответом на второй вопрос будет - первый ход выигрывающего игрока (9,1), так как именно этот ход приводит к проигрышным ходам для второго игрока на втором ходу.
| Начальная позиция | Ходы первого игрока |
| (3,1) | (9,1) |
| (3,3) | |
| (5,1) | |
| (3,3) |
2 ход - второй игрок
Повторяющиеся ходы первого игрока не рассматриваем.
| Ходы первого игрока | Ходы второго игрока |
| (9,1) | (27,1) |
| (9,3) | |
| (11,1) | |
| (9,3) | |
| (3,3) | (9,3) |
| (3,9) | |
| (5,3) | |
| (5,1) | (15,1) |
| (5,3) | |
| (7,1) | |
| (7,3) |
3 ход - первый игрок
| Ходы второго игрока | Ходы первого игрока |
| (27,1) | (81,1) |
| (27,3) | |
| (29,1) | |
| (27,3) | |
| (9,3) | (27,3) |
| (9,9) | |
| (11,3) | |
| (11,5) | |
| (11,1) | (33,1) |
| (11,3) | |
| (13,1) | |
| (11,3) | |
| (5,3) | (15,3) |
| (5,9) | |
| (7,3) | |
| (5,5) | |
| (15,1) | (45,1) |
| (15,3) | |
| (17,1) | |
| (15,3) | |
| (7,1) | (21,1) |
| (7,3) | |
| (9,1) | |
| (7,3) | |
| (7,3) | (21,3) |
| (7,9) | |
| (9,3) | |
| (7,5) |
Выделенные ходы являются выигрышем первого игрока. Соответственно ходы: (27,1), (9,3), (11,1), (15,1) являются проигрышными для второго игрока. По условию задачи - игра безошибочная второй игрок эти ходы не сделает. Но если на первом ходу первый игрок пойдёт (9,1), то у второго игрока на втором ходу не будет других вариантов, как пойти проигрышными ходами (27,1), (9,3) и (11,1). Соответственно, на третьем ходу выиграет первый игрок. Ответом на первый вопрос будет - при безошибочной игре выигрывает игрок, делающий первый ход. На третьем ходу первый игрок выигрывает.
Ответом на второй вопрос будет - первый ход выигрывающего игрока (9,1), так как именно этот ход приводит к проигрышным ходам для второго игрока на втором ходу.