Balls and Boxes

Question

Three urns contain marbles. Each urn is large enough to hold all the marbles . The only operation allowed is to move marbles from an urn to another urn, such that the number of marbles in the receiving urn is doubled. Prove that it is possible, regardless of the initial configuration, to obtain a configuration where one urn is empty.

This is an exercice from a french old book. I’ve been trying to solve it since 3 years without any issue.

Answer 1

This problem is nearly identical to problem 5 of round 1 of the 2011-2012 USAMTS competition. They phrased it slightly differently, as their goal was to get two urns (which they called stacks of cards) to have an equal number, but from this configuration you can easily make one urn empty.

The solution is available in this pdf.

Here is a more condensed version of the proof. The general strategy is to identify classes of scenarios in which victory is achievable and then work to broaden them until every possible scenario is covered.

Let $x$, $y$, $z$ represent the three numbers of balls in the urns, and without loss of generality assume that $x \le y \le z$.

Case 0: $x = 0$ or $x = y$ or $y = z$

Victory is trivial in this cases.

Case 1: $0 < x < y < z$ where $y = nx$ for some integer $n$

We can use the following process to win the game:

• While $x$ and $y$ are unequal
  • If $n$ is currently even, double $x$ by moving balls from urn $z$. This divides $n$ by 2.
  • If $n$ is currently odd, double $x$ by moving balls from urn $y$. This divides $n$ by 2, rounding down.

No matter the starting value of $n$, we eventually reach $n = 1$ which is Case 0.

Case 2: $0 < x < y < z$ where $y = nx + r$ for some integer $n$ and some remainder $0 < r < x$

The same algorithm as in Case 1 is used. Once that algorithm terminates, we are not left with two equal urns, but rather urn $y$ contains exactly $r$ more ball than urn $x$. This is because the presence of the extra $r$ balls present in urn $y$ at the start of the algorithm are completely untouched throughout the process.

Once we have the situation where $y_{new} = x_{new} + r$, we can double urn $x$ from $y$, leaving that urn to now have only $r$ balls remaining. Since $r$ is less than the original value of $x$, we are left with a situation where one of our urns has fewer balls than any urns we began with.

Since the algorithm described in case 2 results in a strictly decreasing sequence of number of balls in the smallest urn, it is impossible to repeat this process indefinitely, and therefore must eventually end up in Case 1 or 0, so this algorithms always terminates.