Задание 137 ГДЗ Семенов Рудченко 6 класс (Информатика)
- Реши задачу, используя поиск выигрышной стратегии в игре. Алёша Попович и Добрыня Никитич воюют с девятиглавым змеем. По очереди богатыри ходят к его пещере, отрубают 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$$ головы и добрать последние головы следующим ходом.
Ответ
Алеше нужно первым ходом отрубить 1 голову, затем после хода Добрыни оставить ему 4 головы и добрать последние головы следующим ходом.
