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

Задача

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

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

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

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

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

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

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

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

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