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

Имеются две кучки камней: в первой 2012 монет, во второй — 2021 монета. Арман и Бахытжан играют в такую игру. За один ход игрок из любой кучки берёт 2, 3 или 4 монеты, а затем добавляет 1 монету во вторую кучку. Проигрывает тот игрок, который не может сделать ход. Арман и Бахытжан ходят по очереди. Начинает Арман. Кто выигрывает при правильной игре?

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

Ответ: Победит Бахытжан.

Докажем, что Бахытжан может всегда удерживать разницу в $9$ камней между кучами, до момента пока в меньшей из куч не станет меньше $4$ камней:

Изначально она равна $9$.Пусть после очередного хода Бахытжана в первой кучке стало $n$ монет, а во второй $n+9$. Тогда у Армана есть 2 варианта хода:

$1)(n,n+9) \rightarrow (n-y,n+10)$

$2)(n,n+9) \rightarrow (n+1,n-y+9)$

Бахытжан в свою очередь делает следующее:

$1)(n-y,n+10) \rightarrow (n-y+1,n-y+10)$

$2)(n+1,n-y+9) \rightarrow (n-y+1,n-y+10)$

Очевидно, что если $n\geq 4$, то Бахытжан может делать такие ходы, а следовательно и удерживать разницу в $9$ камней между кучами. Теперь рассмотрим случаи, что после очередного хода Бахытжана в первой кучке количество камней не превышает $3$:

$1) n=2;3;$, если Арман заберет из первой кучи, то Бахытжан сможет вернуть разницу в $9$ камней между кучами по стратегии показанной выше. Если Арман заберет $2$, $3$ или $4$ камня из второй кучи, то Бахытжан забирает $4$, $3$ или $2$ камня из второй кучи соответственно. Тогда во второй куче количество камней уменьшится на $6$, а в первой увеличиться на $2$. Разница между количеством камней в кучах уменьшится на $8$, то есть станет равна $1$. Эти две кучи будут выглядеть так: $(n,n+1)$. Пока так и оставим, докажем что во втором случае мы сможем привести к такому же виду.

$2) n=0;1;$. В этом случае Арман не сможет забрать из первой кучи, ему придется взять из второй, выше в первом случае показано как тогда сделать кучи вида $(n,n+1)$.

Теперь покажем что Бахытжан всегда сможет после себя оставлять кучи вида $(n,n+1)$:

Пусть после какого-то хода Бахытжана кучи имеют в себе $n$ и $n+1$ камней, тогда Арман может сделать два хода:

$1)(n,n+1) \rightarrow (n-y,n+2)$

$2)(n,n+1) \rightarrow (n+1,n-y+1)$

На что Бахытжан делает следущее:

$1)(n-y,n+2) \rightarrow (n-y+1,n-y+2)$

$2)(n+1,n-y+1) \rightarrow (n-y+1,n-y+2)$

Разница между количеством камней в кучах так и остается равна $1$. Так как в обоих случаях $y\leq n+1$, то если Арман смог сделать ход, то и Бахытжан может. Значит Бахытжан не проиграет, а так как после каждого хода количество камней уменьшается, то Арман проиграет, а Бахытжан выиграет.

А если Арман также будет удерживать разницу в 10 между двумя кучами то и он может выиграть?

Арман же сделает ход первый, если Арман хочеть так делать, у Бакытжана есть всегда контр ход