Thursday, December 17, 2009

Solution: Stones and Marbles

Original problem: here

First, I apologize that the problem was not carefully worded. The problem statement should have been: find all initial conditions where it's always possible for Bob to empty all the three boxes.

There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.

At each step, Bob is allowed to either:

1. take a stone from one box, a marble from another box, and put them on the third box

2. add or subtract all boxes by the same number of stones

3. add or subtract all boxes by the same number of marbles

Prove or disprove, that by repeating these steps, Bob can empty all three boxes.

Solution

Answer: If the total number of objects (stones + marbles) in each box is congruent to each other modulo 3.

Proof:

We can generalize the problem by replacing 2010 with $n$, and it is easy to see that if $n$ is not divisible by 3, then Bob will never be able to empty the boxes, since each operation does not change the total number of objects modulo 3.

Furthermore, even if $n$ is divisible by 3, and we have 2 boxes where they are not congruent to each other modulo 3, Bob will also not be able to empty the boxes. Clearly steps 2 and three does not change relative congruency mod 3, and the first step can be thought as reducing 1 object from each box and adding 3 objects to one box, which again does not change relative congruency mod 3.

Now, suppose the number of total objects in each box is congruent to each other mod 3, we will show that one can always achieve three empty boxes.

Label the boxes as 1,2, and 3. We will denote $A(x,y)$ as the operation of taking a marble from box $x$, a stone from box $y$, and putting them in the third box. We denote the configuration of the boxes at any time by a six-tuple $(m_1, s_1, m_2, s_2, m_3, s_3)$ where $m_i, s_i$ represent the number of marbles and stones in box $i$ respectively. For the time being, we shall also allow negative numbers in the boxes, because due to steps 2 and 3, we can always raise all numbers by the same amount temporarily.

We also denote the change caused by an operation as a six-tuple similar to the one above, but with a square bracket. For example, $A(1,2) = [-1,0,0,-1,1,1]$ means that the operation $A(1,2)$ reduces the number of marble in box 1 by 1, number of stones in box 2 by 1, and increases the number of marbles and stones in box 3 by 1, and leaves everything else unchanged. This is true by definition.

Now, note that:

$A(1,2) = [-1,0,0-1,1,1]$

$A(2,3) = [1,1,-1,0,0,-1]$

$A(1,3) = [-1,0,1,1,0,-1]$

So $A(1,2)+A(2,3)+A(1,3) = [-1,1,0,0,1,-1]$ which means that the composition of the above 3 operations has the effect equivalent of switching a marble in box 1 with a stone in box 3. So now we can define a new operation $B(x,y)$ as switching the marble in box $x$ with a stone in box $y$, using the algorithm described above.

Starting with an initial configuration of arbitrary placement, our first goal is to obtain a configuration in the form of $(a,a,b,b,c,c)$. We can first apply $B(1,2)$ or $B(2,1)$ repeatedly until number of stones and marbles in box 1 are equal or differ by 1. Then we can apply $B(2,3)$ or $B(3,2)$ repeatedly until the number of stones and marbles in box 2 are equal or differ by 1. Because the total number of stones and marbles are equal, this must mean that the number of stones and marbles in box 3 differ by at most 2. We now have 2 cases:

1. We have a configuration in the form of $(a, a+1, b+1, b, c, c)$ or its permutation. Then we apply $A(2,1) = [0,-1,-1,0,1,1]$ to arrive at $(a,a,b,b,c+1,c+1)$ which has the required form.

2. We have a configuration in the form of $(a, a+1, b, b+1, c+2, c)$ or its permutation. We apply $B(3,2) = [0,0,1,-1,-1,1]$ to arrive at $(a,a+1, b+1,b, c+1,c+1)$ which reduces us to case 1.

So now we have a configuration in the form of $(a,a,b,b,c,c)$ where $a \equiv b \equiv c \mod 3$ (by the invariance principle outlined in the beginning).

Now note that:

$A(1,2) = [-1,0,0-1,1,1]$

$A(2,1) = [0,-1,-1,0,1,1]$

$A(1,3) = [-1,0,1,1,0,-1]$

$A(3,1) = [0,-1,1,1,-1,0]$

So $A(1,2)+A(2,1) + A(1,3)+A(3,1) = [-2,-2,1,1,1,1]$, which is equivalent to taking 2 marbles and 2 stones from box 1, and putting 1 of each in box 2 and 3. Let us define $C(x)$ as the operation of taking 2 marbles and 2 stones from box $x$ and putting 1 of each in the two other boxes.

If we let $d = \max (a,b,c) - \min (a,b,c)$. If $d = 0$, then we are done, because that means all three boxes have equal content, and we can repeatedly apply steps 2 and 3 to empty the boxes. But if $d > 0$ we claim that judicious use of operation $C(x)$ will always reduce $d$. Indeed, without loss of generality, we may assume $a \leq b \leq c$. We have 2 cases:

1. If $a \leq b < c$, we apply $C(3)$, then $(a,a,b,b,c,c)$ becomes $(a+1,a+1,b+1,b+1, c-2,c-2)$. But since $c \equiv b \mod 3$, then $c-b \geq 3 \iff c-2 \geq b+1 \geq a+1$ which means now $d' = (c-2)-(a+1) = (c-a)-3 = d-3$.

2. If $a < b \leq c$, we apply $C(2) + C(3)$, then $(a,a,b,b,c,c)$ becomes $(a+2,a+2,b-1,b-1,c-1,c-1)$. But since $b \equiv a \mod 3$, then $b-a \geq 3 \iff a+2 \leq b-1 \leq c-1$ which means now $d' = (c-1)-(a+2) = (c-a)-3 = d-3$.

Thus, we can always reduce $d$ by 3 at a time until we get the configuration where $d = 0$ when all three boxes have equal content. At that point, we can repeatedly apply steps 2 and 3 to empty them.