МОШ 2024, 11 класс, задача 3
Имеется кучка из камней. Двое играют в следующую игру. Первый игрок забирает камень, потом второй может забрать или камня, потом первый может забрать , или камня, затем второй , , или камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл соперник?
(Л. Смирнова)
Ответ
Ответ: первый игрок.
Решение. Докажем, что для любого натурального первый игрок на своём -ом ходе может добиться, чтобы количество забранных из кучки камней равнялось , и второй игрок не сможет ему помешать. Доказательство проведём индуктивно. В свой первый ход первый игрок забирает один камень, т. е. число забранных камней равно . Пусть в свой -й ход первому игроку удалось сделать так, чтобы количество забранных камней равнялось . В свой -й ход второй игрок может взять от до камней. Поскольку , после его хода общее количество забранных камней будет больше и меньше . Первый игрок в свой следующий ход может взять от до камня и точно сможет получить забранных камней независимо от предыдущего хода второго игрока. Таким образом, поскольку , побеждает первый игрок: ему достаточно каждый раз забирать такое число камней, чтобы общее число забранных камней было точным квадратом, и на своём -м ходе он возьмёт последний камень.
Комментарий. Если исходная кучка содержит от до камней, то выигрышная стратегия есть у первого игрока, а если от до , то у второго.