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

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

Рассмотрим позиции по числу оставшихся камней.

Если перед игроком 1 камень, то он вынужден взять его и проигрывает. Значит, позиция с 1 камнем — проигрышная.

Тогда:

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

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

Ответ: выигрывает первый игрок; первым ходом он должен взять 1 камень.