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

Задача

По условию задачи выигрывает тот, кто оставит противнику только один камень.
Первый игрок должен взять первым ходом 1 камень. В кучке останется 5 камей. Второй игрок может взять 1, 2 или 3 камня, в куче останется 4, 3 и 2 камня. Первый игрок вторым ходом сделает своим ходом в куче 1 камень, взяв из кучи 3, 2 или 1 камень. Второму игроку придется забрать последний камень и он проигрывает.
6-5-4-1 – выигрывает первый игрок
6-5-3-1 – выигрывает первый игрок
6-5-2-1 – выигрывает первый игрок
Другим первым ходом первый игрок не обеспечит себе выигрыш.
6-4-1 – первый игрок проигрывает;
6-3-1 – первый игрок проигрывает.

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

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

Если первый игрок возьмёт 1 камень, то в куче останется $$5$$ камней. Второй игрок может взять $$1$$, $$2$$ или $$3$$ камня, и тогда останется $$4$$, $$3$$ или $$2$$ камня. После этого первый игрок своим следующим ходом сможет оставить сопернику $$1$$ камень:

если осталось $$4$$ камня, первый игрок берёт $$3$$;
если осталось $$3$$ камня, первый игрок берёт $$2$$;
если осталось $$2$$ камня, первый игрок берёт $$1$$.

Значит, при первом ходе в $$1$$ камень первый игрок гарантирует победу.

Проверим другие первые ходы:

если первый игрок возьмёт $$2$$ камня, останется $$4$$ камня, и второй игрок сможет оставить $$1$$ камень первому;
если первый игрок возьмёт $$3$$ камня, останется $$3$$ камня, и второй игрок также сможет оставить $$1$$ камень первому.

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