В куче nn камней, играют двое. За ход можно взять из кучи количество камней, либо равное простому делителю текущего числа камней в куче, либо равное 1. Выигрывает взявший последний камень. При каких nn начинающий может играть так, чтобы всегда выигрывать, как бы ни играл его соперник?
Давайте начнем с самого простого случая: n=1. В этом случае в куче есть только один камень, и так как игроки могут брать только 1 камень или простой делитель, то ни один игрок не может сделать ход. Это означает, что ни один игрок не может выиграть в этой ситуации.
Теперь рассмотрим случай n=2. Игрок, который начинает, может взять только один камень, и второй игрок не может сделать ход. Значит, игрок, начинающий игру, всегда выигрывает, когда в куче 2 камня.
Для того, чтобы понять, какую стратегию выбрать, если n больше 2, давайте рассмотрим несколько следующих значений n.
n=3: Игрок, начинающий игру, может взять только 1 камень. Затем второй игрок не сможет сделать ход, так как останется только 1 камень, и это выигрышная ситуация для первого игрока.
n=4: Первый игрок может взять 1 камень. Теперь второй игрок может взять 1 камень или 2 камня (которое является простым делителем для 2). В любом случае, первый игрок делает ход и берет оставшийся камень, получая выигрышную ситуацию.
n=5: Первый игрок может взять 1 камень. Теперь второй игрок может взять только 1 камень, и это выигрышная ситуация для первого игрока.
n=6: Первый игрок может взять 1 камень. Теперь второй игрок может взять 1 камень или 3 камня (3 является простым делителем для 6). В любом случае, первый игрок делает ход и берет оставшийся камень, получая выигрышную ситуацию.
n=7: Первый игрок может взять 1 камень. Теперь второй игрок не сможет сделать ход, так как останется только 1 камень, и это выигрышная ситуация для первого игрока.
Итак, по результатам проведенного анализа мы видим, что первый игрок всегда может выбрать такое число камней, чтобы противник не смог сделать ход и оставить только один камень. Таким образом, если число камней в исходной куче является простым числом, то начинающий игру игрок всегда выиграет.
Однако, если число камней в исходной куче является составным числом, то первый игрок не может выбрать такое число камней, чтобы противник не смог сделать ход и оставить только один камень. В этом случае первый игрок всегда проигрывает и оптимальная стратегия для него - выбирать число камней, равное простому делителю исходного составного числа.
Итак, ответ на вопрос: начальные числа nn, для которых начинающий игрок всегда может выигрывать, являются простыми числами. Во всех остальных случаях первый игрок всегда проигрывает, если оппонент владеет игрой.