Problem: (1998 MOP Rookie Contest, Gabriel Carroll Original) Given a row of $n$ squares ($n > 1$) we place stones in some squares so that no square contains more than one stone. We define the following operation: First, for each square containing a stone (other than the rightmost square), we add a stone to the square to its right. Then, if any square contains $> 1$ stone, remove two stones from it and add a stone to the square on its right (if this square exists). Repeat this second step until each square has at most one stone.
Now, we start with initial configuration $C$ of stones and apply the operation repeatedly. After an odd number of iterations $C$ reappears. Show that $C$ contains at most one stone.
Solution: Consider assigning values to the squares such that any stone in the square has that value. Let the $ k $th square have value $ 2^k $. Now look at the stone farthest to the left. Call the position of this stone $ m $. It clearly never changes under the operation, and each iteration places a stone to the right of it. So take the sum of all the stones $ \pmod{2^{m+2}} $ and call it $ S $. Obviously any addition of stones beyond the $ m+1 $ spot does not affect $ S $ and the second part of the operation doesn't affect $ S $ either by virtue of our numbering (it's invariant under this part of the operation). So we find that $ S $ is affected only by addition of stones in the $ m+1 $ spot (since there are no spots before that are affected). But we said that every iteration a stone is placed in this spot and if there are an odd number of iterations, say $ 2p+1 $ of them, $ S $ increases by $ (2p+1)2^{m+1} = p \cdot 2^{m+2}+2^{m+1} \equiv 2^{m+1} \pmod{2^{m+2}} $ and we find that $ S $ changes. But clearly if we have the initial configuration $ S $ must be the same. That means the $ m+1 $ spot can't exist, or that there can only be one stone, in the $ n $ spot. QED.
--------------------
Comment: The key step in this problem is applying the numbering so that the sum is invariant under the second part of the operation. After this and using mods we basically don't have to worry about what happens with everything beyond the first stone.
--------------------
Practice Problem: (Olympiad Problem Solving Class) Six pieces are placed in the first quadrant in the six squares closest to the origin. Each turn, we may take one piece away and replace it with two pieces in the two squares directly to the right and above the square we took the piece away from. Prove that we can never remove all pieces from the original six squares. Is it possible with just pieces in the three closest squares with a finite number of moves? [Reworded]
Assign the square centered at (1/2, 1/2) a value of 1; and for any square centered at (x+1/2, y+1/2), assign such a square the value of (1/2)^(x+y).
ReplyDeleteNote that in each turn, replacing the piece in (m+1/2, n+1/2) with two pieces in (m+3/2, n+1/2) and (m+1/2, n+3/2) will keep the sum of the values of the occupied squares constant, so the sum of the values of the occupied squares is an invariant.
In the beginning formation, it is clear that the sum of the values is 1 + 2 (1/2) + 3 (1/4) = 2.75.
But the sum of the values in every square in the first quadrant is 4, so removing the pieces from the original six squares would require a sum-value of at most 1.25, which is impossible since the sum-value is an invariant.
With similar reasoning, we see thatthe three squares closest to the origin have a sum-value of 2; but since the infinite first quadrant itself has a sum-value of 4, removing pieces from the three closest squares would require an infinite expansion, and thus impossible to accomplish in a finite number of moves.