Задание 26. Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй — 6 камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче, или добавляет 2 камня в какую-то кучу.
Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 24. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение.
Выигрывает первый игрок, своим первым ходом он должен добавить 2 камня в первую кучу. Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделённые запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучах соответственно.
|
|
2-й ход |
3-й ход |
4-й ход |
5-й ход |
|
|
Позиция после первого хода |
II-й игрок (все варианты хода) |
I-й игрок (выигрышный ход) |
II-й игрок (все варианты хода) |
I-й игрок (один из вариантов) |
Пояснение |
|
5.6 |
5,8 |
7.8 |
14,8 |
28,8 |
Первый игрок выигрывает на пятом ходу, после любого ответа второго игрока, например, удвоив число камней в самой большой куче |
|
9,8 |
18,8 |
||||
|
7,16 |
7,32 |
||||
|
7,10 |
7,20 |
||||
|
7,6 |
7.8 |
Те же варианты четвёртого-пятого ходов |
|||
|
5,12 |
5.24 |
Первый игрок выиграл |
|||
|
10,6 |
20,6 |
Первый игрок выиграл |
|||
Таблица содержит все возможные варианты ходов второго игрока. Из неё видно, что при любом ответе второго игрока у первого имеется ход, приводящий к победе.
Другие задания:
Для наших пользователей доступны следующие материалы: