Упр.3.46 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

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

Рассмотрим позиции по числу камней в кучке.

Если в кучке остался 1 камень, то игрок, которому ходить, вынужден взять его и проигрывает. Значит, позиция с $$1$$ камнем — проигрышная.

Тогда:

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

Следовательно, при безошибочной игре выигрывает первый игрок.

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

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

Ответ: выигрывает первый игрок; первым ходом он должен взять 1 камень.