Balkan Mathematical Olympiad

By ${\nu }_2(n)$ we denote the largest nonnegative integer $r$ such that $2^r\mid n$. A position $(a,b)$ (i.e. two piles of sizes $a$ and $b$) is said to be $k$-happy if ${\nu }_2(a)={\nu }_2(b)=k$ for some integer $k\ge 0$, and $k$-unhappy if $\min \{{\nu }_2(a),{\nu }_2(b)\}=k<\max \{{\nu }_2(a),{\nu }_2(b)\}$. We shall prove that Bob has a winning strategy if and only if the initial position is $k$-happy for some even $k$.

Given a $0$-happy position, the player in turn is unable to play loses.

Given a $k$-happy position $(a,b)$ with $k\ge 1$, the player in turn will transform it into one of positions $(a+\frac{1}{2}b,\frac{1}{2}b)$ and $(b+\frac{1}{2}a,\frac{1}{2}a)$, both of which are $(k-1)$-happy because $${\nu }_2(a+\frac{1}{2}b)={\nu }_2(\frac{1}{2}b)={\nu }_2(b+\frac{1}{2}a)={\nu }_2(\frac{1}{2}a)=k-1.$$ Therefore, if the starting position is $k$-happy, after $k$ moves they will get stuck at a $0$-happy position, so Bob will win if and only if $k$ is even.

* Given a $k$-unhappy position $(a,b)$ with $k$ odd and ${\nu }_2(a)=k<{\nu }_2(b)=l$, Alice not play to position $(\frac{1}{2}a,b+\frac{1}{2}a)$, because the new position is $(k-1)$-happy and will lead to Bob's victory. Thus she must play to position $(a+\frac{1}{2}b,\frac{1}{2}b)$. We claim that this position is also $k$-unhappy. Indeed, if $l>k+1$, then ${\nu }_2(a+\frac{1}{2}b)=k<{\nu }_2(\frac{1}{2}b)=l-1$, whereas if $l=k+1$, then ${\nu }_2(a+\frac{1}{2}b)>{\nu }_2(\frac{1}{2}b)=k$.

Therefore a $k$-unhappy position is winning for Alice if $k$ is odd, and drawing if $k$ is even.