# Marble game theory

In a game, there exist three piles of marbles, each pile with ,a,b, and c marbles respectively, where a,b,c are natural numbers and all different. At each turn, you can double the number of marbles in one pile by transporting marbles from one other larger pile (relative to the pile that is going to be doubled, before the doubling). The game is won when any two of the piles have an equal number of marbles.

Either show that the game can be won from any starting a,b,c, or prove that this is not the case. (In particular, prove that the game cannot be won from every starting a,b,c.)

An interesting one, but the solution come does not.

Ernst

-

A duplicate of this question, Emptying buckets by moving pebbles around, was asked (and, interestingly, received a lot more upvotes than this one). Before Brian pointed out that it was a duplicate, I came up with a solution different from the shortlist solution. (I treat the problem of emptying one of the piles, which, as discussed in Phira's answer and comments, is equivalent.)

The idea is to successively produce $0$s in the binary representations of two of the numbers, starting with the least significant bit. So assume that the last $k$ bits of $b$ and $c$ are already zero; then if neither $b$ nor $c$ is zero yet, our aim is to make the last $k+1$ bits of two of the numbers zero.

So consider the $(k+1)$-th bits of $b$ and $c$. If they're both $0$, we're done. If they're both $1$, we just need one transfer between $b$ and $c$ to make them both $0$. If one is $0$ and one is $1$, we can put the $1$ in the lesser of the two by transferring from the greater to the lesser until it becomes the lesser.

Without loss of generality, assume $b\lt c$. Now there are two cases. If $a\ge b$, we can get rid of the $1$ by a transfer from $a$ to $b$. Otherwise, $a\lt b\lt c$, and we transfer first from $b$ to $a$ and then from $c$ to $b$, thus going from $a,b,c$ to $2a,b-a,c$ to $2a,2(b-a),c+a-b$. Now the sum of the first two numbers is $2b$, which has $0$s in the last $k+1$ bits, so we can make the last $k+1$ bits of those two numbers $0$ by making transfers between them, each of which gets rid of their last $1$ bits.

If we initially assign $a$, $b$ and $c$ such that $a$ has the fewest final zeros, this strategy seems to be slightly more efficient than the shortlist strategy: Compared to the total of $103505$ transfers minimally required to solve all distinct instances with totals less than $100$, this strategy makes $172865$ transfers while the shortlist strategy makes $190994$.

-
The $2b$ trick is nice. ($2b$ or $\lnot 2b\dots$) –  Brian M. Scott Dec 8 '11 at 21:33
:-) ${}{}{}{}{}$ –  joriki Dec 8 '11 at 21:39

For strictly positive numbers this is essentially problem C3 of the IMO shortlist 1994 where we want to empty an account in the same situation. (Because you have to have two equal amounts before an amount can get zero.)

There are several websites that offer shortlist solutions, for example:

http://mks.mff.cuni.cz/kalva/short/soln/sh94c3.html

I don't know if I am supposed to copy a solution here.

-
Presumably, "natural numbers" here is meant to exclude 0 (pretty common usage). –  Alon Amit Oct 9 '11 at 8:54
For natural number read positive integer. It’s a regrettably common usage. –  Brian M. Scott Oct 9 '11 at 9:02
Positive is also not always advisable as there are languages/countries where 0 is positive and negative. –  Phira Oct 9 '11 at 9:09
@Brian M.Scott Note that the IMO problem has two parts. The first part is about emptying just one of the three accounts which is exactly equivalent to making two accounts the same size. –  Phira Oct 10 '11 at 7:22
You’re right. $\quad$ –  Brian M. Scott Oct 10 '11 at 7:42