Областная олимпиада по математике, 2006 год, 10 класс

Имеется куча из $N > 1$ камней. Двое играют в игру. За один ход можно либо забрать один камень из любой кучи, либо разделить любую имеющуюся кучку на две произвольным образом (если в куче более одного камня). Побеждает тот, кто заберет последний камень. Кто из соперников сможет победить независимо от игры соперника?

Комментарий/решение

В куче в начале игры может быть как четное, так и нечетное количество камней. Рассмотрим эти случаи по отдельности. Пусть в кучп количество камней четно, то есть $N=2n$. Игру начинает первый игрок. Если он заберет камень, то его соперник будет в сильной позиции, ведь камней останется $2n-1$ , и последний камень поднимет второй игрок. Значит, первому игоку придется делить кучу на две. Второй игрок считает камни, видит, что если он возьмет камень, тов конце концов последний камень поднимет первый игрок. Он также делит одну из этих куч надвое. Таким образом, игроки делят кучи, пока не останутся $2n$ куч с одним камнем. Причем таких делений будет $2n-1$, то есть первым возьмет камень второй игрок, из чего следует, что победит первый.

Пусть в куче $2n+1$ камней. Первому игрокк брать камни нельзя, ведь игра сведется к случаю $2n$ , только первым начнет ее второй игрок. Значит, первый игрок делит кучу надвое. Второму игроку брать камни не стоит по той же причине. Таким образом, произойдет $2n$ делений, то есть первым забирает камень первый. Но теперь-то все кучи разделены, изменить ход событий второй игрок уже не может. $2n+1$ый камень поднимет первый игрок.

Ответ:победит первый игрок

Неверно, при N нечетном победит второй, при четном победит первый соответственно. Доказательство через индукцию.