ГДЗ по информатике 11 класс Босова, номер §11 № 4

§ № Игра со спичками

На столе лежит 25 спичек. Играют двое. Игроки по очереди могут взять от одной до четырёх спичек. Кто не может сделать ход (так как спичек не осталось), проигрывает. Другими словами, выигрывает взявший последнюю спичку. Выясните, у кого из игроков есть выигрышная стратегия.

Решение

Назовём проигрышной позицию, из которой игрок при любом своём ходе отдаёт сопернику возможность победить. Если осталось спичек, игрок может взять , , или , оставив соответственно , , или спичку. Соперник заберёт все оставшиеся. Значит, — проигрышная позиция для того, кому предстоит ход.

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

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

Следовательно, при правильной игре выигрывает второй игрок.

Ответ

Выигрышная стратегия есть у второго игрока: дополнять каждый ход первого до спичек.

Помогло?

Номер §11 № 4