Wednesday, December 16, 2009

Stones and Marbles

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.

1. Here's a method to determine if it's NOT possible:

Assign a weight to each box: -1, 0 and 1. Consider the weighted sum mod 3 of the marbles and stones in each box, where S = -1 * (m_{-1} + s_{-1}) + ) + 0 * (m_0 + s_0) + 1 * (m_1 + s_1) mod 3. Observe that S is invariant across the three possible operations.

Now, if the boxes can be emptied, then one must be able to reach the initial configuration of stones and marbles from the state of having none. Since S is invariant, if the initial configuration has a nonzero mod 3 weighted sum then it cannot be reached from the empty state.

In this case 4020 mod 3 = 0, so it's possible that the boxes can be emptied. I'm guessing that the answer is yes :P Somehow have to prove that mod 3 weighted sum equivalence => reachable configuration.

2. Ok part 2. We show that mod3 weighted sum equivalence => can reach same configuration.

Consider marbles in three boxes: m_{-1}, m_0, m_1. Let k = m_1 - m_0, where we assume without loss of generality that m_1 >= m_0. Now, the configuration is (m_{-1}, m_0, m_0 + k), which is equivalent to (m_{-1} + k, m_0, m_0), which is equivalent to (m_{-1} - m_0 + k, 0, 0).

Secondly, observe that we can go from (x,0,0)(x+1,1,1)(x+2,0,1)(x+3,0,0). With this second observation, we can say that there are only 3 configurations - every configuration can be reduced to one of these three: (0,0,0),(1,0,0) and (2,0,0).

Now, given that we have two separate initial configurations with the same mod3 weighted sum. Assume that we cannot reach the same configuration from both of these states. However, from above both of these reduce to a form (x,0,0) and (x',0,0) where x mod 3 = x' mod 3. This must reduce to exactly one of (0,0,0),(1,0,0) or (2,0,0) so they are in fact the same configuration. Hence, the weighted sum condition is necessary and sufficient so for the case of 2010 marbles/stones it is possible to empty the boxes.

3. Actually, the above showed that it's possible if we just consider just one of marbles or stones. Probably need to extend the argument since operation 1 actually involves stone+marble simultaneously.

4. Your necessity condition (invariant argument) is correct. But sufficiency condition is still too simplistic. You need to consider both marbles AND stones at the same time, because even if after a series of operations you get the marbles to "even out", the stones may be messed up. And in the process of evening out the stones, you may mess up the marbles as well.

5. [...] Original problem: here [...]