ГДЗ по информатике 9 класс Босова, номер §2.4 № 5

§. № Выигрышная стратегия в игре с камнями

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

Решение

Обозначим положение парой (первая куча, вторая куча). Исходное положение — (, ), сумма . Первый игрок может утроить первую кучу или прибавить к ней камня — в обоих случаях получится (, ). Утроение второй даёт (, ), прибавление к ней камней — (, ). Во всех трёх положениях сумма меньше , поэтому первым ходом выиграть нельзя.

Для каждого варианта найдём ответ второго игрока:

Первый ход: положение	Ответ второго: положение	Почему ответ выгоден
(, )	(, )	прибавить ко второй куче
(, )	(, )	утроить вторую кучу;
(, )	(, )	утроить первую кучу

Проверим, почему положение (, ) также обеспечивает победу второму игроку. После его хода первый может получить только (, ), (, ), (, ) или (, ). Суммы равны соответственно , , , : ни одна не достигает . Из (, ) второй утроит первую кучу: . Из (, ) утроит вторую: . Из (, ) утроит первую: . Из (, ) утроит вторую: . Во всех случаях второй игрок выигрывает.

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

Ответ

Выигрывает второй игрок. Если первый получил (, ), нужно добавить камня во вторую кучу; если (, ), утроить вторую кучу и выиграть сразу; если (, ), утроить первую кучу.

Помогло?

Номер §2.4 № 5