Three piles, can only move stones if doubles a pile. Prove we can always empty a pile.

Question

This problem is circulating for weeks with no breakthrough.

We are given $3$ piles of stones. The only legal move is to choose a target pile, say of size $k$, and move $k$ stones from some other pile to the target pile. We may repeat this operation. Prove that there always exists a sequence of moves after which a pile will be empty.

Thoughts

• If the quotient between two piles is of the form $2^n-1$ then we can use just these two to finish.

• We may assume that there is no divisor common to all three piles.

• We may bound the maximal quotient of the sizes in the starting position by repeatedly moving stones from the largest pile, but cannot guarantee to stay in this bound later during the solution.

• There seems not to be any obvious semi-invariant like the sum of sizes, sum of squares etc.

Answer 1

Let the sizes of the three piles be $0< a\le b\le c$. Let $b=ka + r$ with $0\le r < a$ and let $(k_m\dots k_0)_2$ be the binary representation of $k$.

Now if $k_0=1$ do the operation with the first and the second pile removing $k_0a$ from $b$, if $k_0=0$ do it with the first and the third pile, again removing $k_0a$ from $b$. Repeat this procedure with $k_1$ removing $k_1\cdot 2a$ from $b$, and so on until $k_m\cdot 2^m a$. This is always possible because $c$ is sufficiently big.

In the end we have reduced $b$ to $r$ which is smaller than the previous minimum $a$. Therefore, repeating this process will eventually reduce the minimum to $0$.

(This is a problem from the 1994 IMO shortlist.)