Упр.46 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)

Задача

Рассмотрим вариант решения задания из учебника Босова 9 класс, Просвещение: 46. Два игрока играют в следующую игру. Перед ними лежит кучка из 6 камней. Игроки берут камни по очереди. За один ход можно взять 1, 2 или 3 камня. Проигрывает тот, кто забирает последний камень. Кто выигрывает при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте, построив дерево игры. Игрок выиграет, если перед ходом противника на столе остался 1 камень. Если первый игрок сделает на столе 5 камней (уберёт один камень), у второго игрока нет выигрышного хода. Если первый игрок оставит на столе 4 или 3 камня – у второго игрока появляются выигрышные ходы, при правильной игре он выигрывает.

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

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

Рассмотрим возможные ходы из начальной позиции $$6$$:

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

Проверим эти позиции:

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

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

Следовательно, первый игрок должен убрать $$1$$ камень.