СПбГУ 2024, 8-9 классы, задача 6
( баллов) Даны четыре кучи камней, занумерованные числами от до . Сначала в каждой куче лежит по камня. Петя и Вася играют в игру. Ходят по очереди, начинает Петя. Каждый ход игрок выбирает натуральные числа , берет камней из кучи с номером и раскладывает все взятые камни, добавляя их по одному камню в каждую из куч с номерами от до . Проигрывает тот, кто не может сделать ход. Кто из игроков может победить независимо от игры соперника?
Ответ
Ответ: Выигрывает Петя.
Решение. Будем следить за количеством камней во второй и четвертой кучах (числа и ). Количество камней в остальных кучах не будет иметь значения. Назовем позицию выигрышной, если игрок, делающий ход из этой позиции, может затем победить. В противном случае позицию назовем проигрышной. Покажем, что позиции, в которых четно, а дает остаток , или при делении на , а также позиции, в которых нечетно, а не дает остаток при делении на , выигрышные. Для этого надо проверить, что из любой выигрышной позиции есть ход в проигрышную позицию, а из любой проигрышной позиции либо вообще нет хода, либо ход есть только в выигрышные позиции. Отметим, что любой ход, в котором камни берутся из второй или третьей куч, на единицу меняет число камней во второй куче и не меняет число камней в четвертой куче, поэтому из проигрышной позиции такой ход заведомо ведет в выигрышную.
| выигрышные | проигрышные | ||
|---|---|---|---|
| четно | четно | ||
| нечетно | нечетно |
Рассмотрим ходы, в которых камни берутся из четвертой кучи. Покажем, что любой такой ход переводит проигрышную позицию в выигрышную. Взятие одного камня из четвертой кучи не затрагивает вторую кучу и меняет остаток от деления на пять, поэтому он заведомо переводит проигрышную позицию в выигрышную. Если из четвертой кучи взято два или три камня, то увеличится на единицу и, в частности, сменит четность. Но если давало остаток при делении на , то уменьшение на два или три приведет к остаткам или , что соответствует выигрышной позиции. Если же давало остаток или от деления на , то уменьшение на два или три не может привести к остатку ( переходит в или , а переходит в или ), что также соответствует выигрышной позиции.
Наконец, покажем, что из выигрышной позиции всегда есть ход в проигрышную. Если нечетно, то надо просто переложить один камень из второй кучи в первую. Если - четно, то дает остаток , или при делении на . Для остатков и можно переложить один камень из четвертой кучи в третью. А для остатка - взять три камня и разложить их по первым трем кучам. Тогда станет нечетным, а будет давать остаток от деления на , что соответствует проигрышной позиции.