Математикадан облыстық олимпиада, 2005-2006 оқу жылы, 10 сынып

$N > 1$ тастан тұратын тас үйіндісі бар. Екі адам ойын ойнайды. Бір жүрісте кез келген тас үйіндісінен бір тас алуға немесе кез келген тас үйіндісін қалағаны бойынша екіге бөлуге болады(егер тас үйіндісінде бір тастан көп болса). Ең соңғы тасты алған адам ұтады. Қарсыласы ойынына тәуелсіз қай ойыншы ұтады?

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

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

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

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

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