Задание 26. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 2, а во второй — 3 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает или в 2 раза, или в 3 раза число камней в какой-то куче.
Выигрывает игрок, после хода которого в одной из куч становится не менее 20 камней. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение.
Выигрывает второй игрок.
Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделённые запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучах соответственно.
|
1-й ход |
2-й ход |
3-й ход |
4-й ход |
|
Стартовая позиция |
I-й игрок (все варианты хода) |
II-й игрок (выигрышный ход) |
I-й игрок (все варианты хода) |
II-й игрок (один из вариантов) |
Пояснение |
2,3 |
4,3 |
4.6 |
8,6 |
24,6 |
Второй игрок выигрывает на четвёртом ходу, после любого ответа первого игрока, например, утроив число камней в самой большой куче |
12,6 |
36.6 |
||||
4,12 |
4.36 |
||||
4,18 |
4,54 |
||||
|
6,3 |
6.6 |
12,6 |
36,6 |
Второй игрок выигрывает на четвертом ходу, после любого ответа первого игрока, например, утроив число камней в самой большой куче |
18,6 |
54.6 |
||||
6,12 |
6.36 |
||||
6,18 |
6,54 |
||||
2,6 |
6.6 |
Те же варианты третьего-четвёртого ходов |
|||
2,9 |
2.27 |
Второй игрок выигрывает ответным ходом |
Таблица содержит все возможные варианты ходов первого игрока. Из неё видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.
Другие задания:
Для наших пользователей доступны следующие материалы: