Игра с камнями: стратегия победы
В куче камней, играют двое. За ход можно взять из кучи количество камней, либо равное простому делителю текущего числа камней в куче, либо равное 1. Выигрывает взявший последний камень. При каких начинающий может играть так, чтобы всегда выигрывать, как бы ни играл его соперник?
Показать ответ
при , не кратном 4.
Разобрать решение
Стратегия: каждый раз оставлять в куче кратное 4 число камней: при надо взять один камень, при — два камня; при надо взять камней, где — простой делитель числа вида (такой есть, иначе все простые делители имеют вид , а произведение чисел такого вида тоже имеет такой вид и не равно ).
Противник из кучи с кратным 4 числом камней не может взять число камней, кратное 4 (это будет не простое число), поэтому начинающий и дальше может играть по стратегии.
Обсуждение
0Комментариев пока нет.