|
|
 |
Условие
В куче 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.
