ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66868
Тема:    [ Теория игр (прочее) ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Автор: Ивлев Б.М.

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

Решение

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

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

Ответ

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

Источники и прецеденты использования

олимпиада
Название Турнир городов
год/номер
Номер 42
Дата 2020/21
вариант
Вариант осенний тур, базовый вариант, 8-9 класс
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .