Задание 137 ГДЗ Семенов Рудченко 6 класс (Информатика)

Задача

Синие позиции проигрышные, красные выигрышные.
Алеша срубает одну голову, остается 8.
Добрыня может срубить любое количество из доступных голов, и в любом случае, предоставляет Алеше выигрышную позицию (5, 6 или 7).
Алеша срубает столько голов, чтобы осталось 4.
Добрыня опять может срубить любое количество из доступных голов, и в любом случае, предоставляет Алеше выигрышную позицию (1, 2 или 3).
Алеша срубает последние (или последнюю) головы.

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

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

Если осталось $$1$$, $$2$$ или $$3$$ головы, то следующий игрок может сразу добрать все головы и выиграть. Значит, эти позиции выигрышные.

Если осталось $$4$$ головы, то можно отрубить $$1$$, $$2$$ или $$3$$ головы и оставить сопернику $$3$$, $$2$$ или $$1$$ голову. Все эти позиции выигрышные для следующего игрока, значит, $$4$$ — проигрышная позиция.

$$5$$, $$6$$, $$7$$ — выигрышные, потому что можно оставить $$4$$;
$$8$$ — проигрышная, потому что любой ход оставляет $$5$$, $$6$$ или $$7$$;
$$9$$ — выигрышная, потому что можно оставить $$8$$.

Значит, Алеше нужно первым ходом оставить Добрыне $$8$$ голов, то есть отрубить $$1$$ голову. Тогда Добрыня неизбежно отдаст Алеше позицию с $$4$$ головами, а затем Алеша сможет оставить $$1$$, $$2$$ или $$3$$ головы и добрать последние головы следующим ходом.