Условие
Имеется кучка из 100 камней. Двое играют в следующую игру. Первый
игрок забирает 1 камень, потом второй может забрать 1 или 2 камня, потом первый
может забрать 1, 2 или 3 камня, затем второй 1, 2, 3 или 4 камня, и так далее. Выигрывает тот, кто забирает последний камень. Кто может выиграть, как бы ни играл
соперник?
Решение
Докажем, что для любого натурального $n\leqslant 10$
первый игрок на своём $n$-м ходе может добиться, чтобы количество
забранных из кучки камней равнялось $n^2$, и второй игрок не сможет
ему помешать. Доказательство проведём индуктивно. В свой первый ход
первый игрок забирает один камень, т. е. число забранных камней
равно $1^2$. Пусть в свой $n$-й ход первому игроку удалось сделать так,
чтобы количество забранных камней равнялось $n^2$. В свой $n$-й ход
второй игрок может взять от 1 до $2n$ камней. Поскольку
$(n+1)^2-n^2=2n+1$, после его хода общее количество забранных камней
будет больше $n^2$ и меньше $(n+1)^2$. Первый игрок в свой следующий
ход может взять от 1 до $2n+1$ камня и точно сможет обеспечить $(n+1)^2$
забранных камней независимо от предыдущего хода второго игрока. Таким
образом, поскольку $100=10^2$, побеждает первый игрок: ему достаточно
каждый раз забирать такое число камней, чтобы общее число забранных
камней было точным квадратом, и на своём 10-м ходе он возьмёт
последний камень.
Ответ
Первый игрок.
Замечания
Если исходная кучка содержит от $n^2$ до $n^2+n-1$ камней, то выигрышная стратегия есть у первого игрока, а если от $n^2+n$ до $n^2+2n$, то у второго.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Московская математическая олимпиада |
|
год |
|
Номер |
87 |
|
Год |
2024 |
|
класс |
|
Класс |
11 |
|
задача |
|
Номер |
3 |
