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

Задача

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

Подробный ответ

Рассмотрим позиции, в которых игрок, которому предстоит ход, проигрывает. Это те случаи, когда он вынужден забрать последний камень.

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

Тогда позиции с $$2$$, $$3$$ и $$4$$ камнями — выигрышные, потому что из них можно оставить сопернику $$1$$ камень:

из $$2$$ взять $$1$$;
из $$3$$ взять $$2$$;
из $$4$$ взять $$3$$.

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

Значит, из начальной позиции $$6$$ камней нужно первым ходом оставить сопернику $$5$$ камней. Для этого надо взять $$1$$ камень.

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