ГДЗ по информатике 8 класс Босова, номер §3.1 ПМ 3

§. ПМ Алгоритм выигрышной игры

Из кучи, содержащей любое, большее 3, количество каких-либо предметов, двое играющих по очереди берут по одному или по два предмета. Выигрывает тот, кто своим очередным ходом сможет забрать все оставшиеся предметы.
Рассмотрим алгоритм, следуя которому первый игрок наверняка обеспечит себе выигрыш.

Если число предметов в куче кратно 3, то уступить ход противнику, иначе начать игру, взяв 1 или 2 предмета так, чтобы осталось количество предметов, кратное 3.
Своим очередным ходом каждый раз дополнять число предметов, взятых соперником, до 3 (число оставшихся предметов должно быть кратно 3).
Предложите сыграть в эту игру кому-нибудь из своих родных, друзей или знакомых. Действуйте строго в соответствии с приведённым выше алгоритмом. Убедитесь, что алгоритм «работает»!

Решение

Проведём пример игры с кучей из предметов. Это допустимое исходное число, потому что . При делении на остаток равен : . По первому шагу алгоритма берём предмета, чтобы оставить предметов; кратно .

Допустим, соперник берёт предмет. Остаётся . По второму шагу алгоритма мы берём , поскольку ; остаётся предмета.

Если теперь соперник берёт предмета, остаётся . Мы берём , потому что . Куча пуста: , и последний ход сделали мы.

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

Вывод: в показанной партии, следуя алгоритму, мы выигрываем.

Ответ

Пример: при предметах берём ; на предмет соперника отвечаем , на — . В приведённой партии выигрываем последним ходом.

Помогло?

Номер §3.1 ПМ 3