Задание 26. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй — 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 4 камня в какую-то кучу. Выигрывает игрок, после хода которого в одной из куч становится не менее 20 камней. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение.
Выигрывает второй игрок.
Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделённые запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучах соответственно.
|
|
1-й ход |
2-й ход |
3-й ход |
4-й ход |
|
|
Стартовая позиция |
I-й игрок (все варианты хода) |
II-й игрок (выигрышный ход) |
I-й игрок (все варианты хода) |
II-й игрок (один из вариантов) |
Пояснение |
|
1,2 |
3,2 |
3,6 |
9,6 |
27,6 |
Второй игрок выигрывает на четвёртом ходу, после любого ответа первого игрока, например, утроив число камней в самой большой куче |
|
7,6 |
21,6 |
||||
|
3,18 |
3,54 |
||||
|
3,10 |
3,30 |
||||
|
5,2 |
5,6 |
15,6 |
45,6 |
Второй игрок выигрывает на четвёртом ходу после любого ответа первого игрока, например, утроив число камней в самой большой куче |
|
|
9,6 |
27,6 |
||||
|
5,18 |
5,54 |
||||
|
5,10 |
5,30 |
||||
|
|
1,6 |
3,6 или 5,6 |
Те же варианты третьего-четвёртого ходов |
||
Таблица содержит все возможные варианты ходов первого игрока. Из неё видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.
Другие задания:
Для наших пользователей доступны следующие материалы: