Задание 14 Параграф 2.3 ГДЗ Босова 9 класс 2023 (Информатика)

При безошибочной игре выигрывает первый игрок.
При любом ходе второго игрока, первый может оставить 1 камень.

Обозначим позицию числом камней в куче. Проигрывает тот, кто берёт последний камень, значит после своего хода нужно оставить сопернику такое число камней, из которого он неизбежно попадёт в проигрышную ситуацию.

Рассмотрим позиции с конца:

• $$1$$ камень — любой ход приводит к взятию последнего камня, значит это проигрышная позиция.
• $$2$$ камня — можно взять $$1$$ и оставить $$1$$ камень сопернику, значит это выигрышная позиция.
• $$3$$ камня — можно взять $$2$$ и оставить $$1$$ камень, значит это выигрышная позиция.
• $$4$$ камня — можно взять $$3$$ и оставить $$1$$ камень, значит это выигрышная позиция.
• $$5$$ камней — любой ход $$1, 2$$ или $$3$$ оставляет сопернику $$4, 3$$ или $$2$$ камня, то есть выигрышные позиции. Значит, $$5$$ — проигрышная позиция.
• $$6$$ камней — можно взять $$1$$ и оставить $$5$$ камней, то есть проигрышную позицию для соперника. Значит, $$6$$ — выигрышная позиция.

Следовательно, выигрывает первый игрок. Первый ход должен быть таким, чтобы оставить в куче $$5$$ камней, то есть нужно взять $$1$$ камень.

Дерево игры можно представить так:

6 → 5 → 4, 3, 2
Из позиции 5 любой ход ведёт к 4, 3 или 2, а из них можно оставить 1 камень.

Ответ

Выигрывает первый игрок. Первый ход: взять $$1$$ камень.