Задача № 1668688, 9, 10, 11 классы3 / 5

Игра с камнями: стратегия победы

В куче nn камней, играют двое. За ход можно взять из кучи количество камней, либо равное простому делителю текущего числа камней в куче, либо равное 1. Выигрывает взявший последний камень. При каких nn начинающий может играть так, чтобы всегда выигрывать, как бы ни играл его соперник?

Показать ответ

при nn, не кратном 4.

Разобрать решение

Стратегия: каждый раз оставлять в куче кратное 4 число камней: при n=4k+1n = 4k + 1 надо взять один камень, при n=4k+2n = 4k + 2 — два камня; при n=4k+3n = 4k + 3 надо взять pp камней, где pp — простой делитель числа nn вида 4q+34q + 3 (такой есть, иначе все простые делители nn имеют вид 4m+14m+1, а произведение чисел такого вида тоже имеет такой вид и не равно 4k+34k+3).

Противник из кучи с кратным 4 числом камней не может взять число камней, кратное 4 (это будет не простое число), поэтому начинающий и дальше может играть по стратегии.

Обсуждение

0

Комментариев пока нет.

Чтобы оставить комментарий, войдите в аккаунт.

Версии задачи

Выберите доступную версию задачи. Текущая версия отмечена в списке.

Сообщить об ошибке

Опишите неточность в условии, ответе или решении задачи № 166868.

Старый дизайн