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