Задача 66868
|
|
 |
Условие
В куче $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 (это будет не простое число), поэтому начинающий и дальше может играть по стратегии.
