Два игрока играют в игру: они по очереди вытаскивают камни из кучки, в которой изначально было n камней. В свой первый ход первый игрок берет из кучи один или несколько камней, но не может забрать все камни. Каждым следующим ходом очередной игрок должен забрать из кучи количество камней, являющееся делителем числа камней, забранного противником на предыдущем ходу, и не превосходящее числа камней в куче. Выигрывает тот, кто заберет последний камень. Для каждого n > 1 определите, у кого из соперников есть выигрышная стратегия.
Two players play a game: they take turns picking stones from a pile that originally contained n stones. On his first turn the first player takes one or more stones from the pile, but cannot take all of the stones. On each next move a player must take the number of stones from the pile, which is a divisor of the number of stones taken by the opponent on the previous move, and does not exceed the number of stones in the pile. The one who takes the last stone wins the game. Determine for each 
which of the opponents has a winning strategy.
Заметим, что если в куче нечетное число камней, то первый игрок гарантирует себе победу, взяв на первом ходу 1 камень: тогда каждым следующим ходом игроки будут забирать по одному камню, и последний камень заберет первый игрок. Когда n чётно, тот, кто первым сделает нечетный шаг, проиграет: такой шаг был сделан из четного числа — значит, он не будет последним, а противник заберет один камень, что и обеспечит ему победу.
Если 
то второй игрок, очевидно, побеждает. Если 
то побеждает первый игрок, забирая первым ходом 1 камень. Если 
то побеждает второй игрок: если первый берет 1 камень, то второй возьмет последний камень, а если первый игрок первым ходом берет 2 или 3 камня, то второй игрок первым своим ходом забирает остальные камни.
Докажем по индукции, что для всех четных n от 
до 
(для натурального 
побеждает первый игрок, а для 
— 
разобрана в предыдущем задании. Пусть 
для натурального 
Тогда первый игрок сводит игру к таковой с 
камнями (т. е. берет вдвое больше камней, чем взял бы в игре с камнями), где у него есть победная стратегия согласно предположению индукции, поскольку 
Единственный способ помешать ему — взять нечетное число камней, но, как показано выше, тот, кто первым возьмет нечетное число камней, проигрывает.
Пусть теперь для Тогда уже второй игрок применяет стратегию «половинчатой», то есть берет в 2 раза больше камней, чем взял бы в игре с камнями. Согласно предположению индукции, это обеспечит ему победу.
Note, that if there is an odd number of stones in the pile, then the first player guarantees himself a victory by taking 1 stone on the first move: then each next move the players will take 1 stone, and the last stone will be taken by the first player. When n is even, the first one to make an odd step will lose: such a step was made from an even number - so it will not be the last one, and the opponent will immediately take 1 stone, which will ensure his victory.
If then the second player wins obviously. If then the first player wins by taking 1 stone on the first move. If then the second player wins: if the first player takes 1 stone, then the second player takes the last stone, and if the first player takes 2 or 3 stones on the first move, then the second player takes the remaining ones.
Lets prove by induction that for all even n from to (while 
is an integer) the first player wins, and for so does the second player. The base of induction has been shown above.
Let for integer Then the first player reduces the game to that with stones (i. e. he takes twice as many stones as he would take in the game with stones), where he has a winning strategy according to the induction hypothesis, since The only way to stop him is to take an odd number of stones, but as shown above, whoever is the first to take an odd number of stones loses.
Let now for Then the second player applies his strategy of the game with stones, i. e. he takes 2 times more stones than he would take in the game with stones. According to the induction hypothesis, this will ensure his victory.
Ответ: при (для 
второй игрок может гарантировать себе победу. При прочих выигрышная стратегия есть у первого игрока.