14. Два игрока играют в следующую игру. Перед ними лежит куча из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте, построив дерево игры.
Ответ
Для определения того, кто выигрывает при безошибочной игре обоих игроков, нам нужно построить дерево игры и проанализировать выигрышные и проигрышные стратегии.
В дереве игры, числа в скобках обозначают оставшееся количество камней в куче после выполнения хода игрока.
Из дерева видно, что игрок, делающий первый ход, имеет выигрышную стратегию. Он может выбрать количество камней таким образом, чтобы оставить своему сопернику 4, 3 или 2 камня на следующем ходу.
Независимо от того, сколько камней выберет первый игрок, соперник всегда сможет выбрать количество камней таким образом, чтобы на следующем ходу оставить первому игроку 3, 2 или 1 камень. Таким образом, первый игрок всегда сможет выбрать количество камней таким образом, чтобы оставить сопернику 2, 1 или 0 камней на следующем ходу.
Из этого можно сделать вывод, что при безошибочной игре обоих игроков выигрывает игрок, делающий первый ход. Его оптимальный первый ход — взять 3 камня.