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