Junior Balkan MO

Solution:

Denote the number of coins in the two piles by $X$ and $Y$. We say that the pair $(X, Y)$ is losing if the player who begins the game loses and that the pair $(X, Y)$ is winning otherwise. We shall prove that $(X, Y)$ is losing if $X-Y \equiv 0,1,7 \pmod{8}$, and winning if $X-Y \equiv 2,3,4,5,6 \pmod{8}$.

Lemma 1. If we have a winning pair $(X, Y)$ then we can always play in such a way that the other player is then faced with a losing pair.

Proof of Lemma 1. Assume $X \geq Y$ and write $X=Y+8k+\ell$ for some non-negative integer $k$ and some $\ell \in\{2,3,4,5,6\}$. If $\ell=2,3,4$ then we remove two coins from the first pile and add one coin to the second pile. If $\ell=5,6$ then we remove four coins from the first pile and add one coin to the second pile. In each case we then obtain a losing pair.

Lemma 2. If we are faced with a losing distribution then either we cannot play, or, however we play, the other player is faced with a winning distribution.

Proof of Lemma 2. Without loss of generality we may assume that we remove $k$ coins from the first pile. The following table shows the new difference for all possible values of $k$ and all possible differences $X-Y$. So however we move, the other player will be faced with a winning distribution.

Since initially the coin difference is $1 \bmod 8$, by Lemmas 1 and 2 Bob has a winning strategy: He can play so that he is always faced with a winning distribution while Ann is always faced with a losing distribution. So Bob cannot lose. On the other hand the game finishes after at most $4017$ moves, so Ann has to lose.