IMO 2001 SL C7

Origin: FRA | Category: Combinatorics

Problem

A pile of n pebbles is placed in a vertical column. This configuration is modified according to the following rules. A pebble can be moved if it is at the top of a column that contains at least two more pebbles than the column immediately to its right. (If there are no pebbles to the right, think of this as a column with 0 pebbles.) At each stage, choose a pebble from among those that can be moved (if there are any) and place it at the top of the column to its right. If no pebbles can be moved, the configuration is called a final configuration. For each n, show that no matter what choices are made at each stage, the final configuration is unique. Describe that configuration in terms of n.

Solution

At any moment, let pi be the number of pebbles in the ith column, i = 1, 2, . . . . The final configuration has obvious properties p1 \geqp2 \geq\cdot \cdot \cdot and pi+1 \in{pi, pi −1}. We claim that pi+1 = pi > 0 is possible for at most one i. Assume the opposite. Then the final configuration has the property that for some r and s > r we have pr+1 = pr, ps+1 = ps > 0 and pr+k = pr+1 −k + 1 for all k = 1, . . . , s −r. Consider the earliest configuration, say C, with this property. What was the last move before C? The only possibilities are moving a pebble either from the rth or from the sth column; however, in both cases the configuration preceding this last move had the same property, contradicting the assumption that C is the earliest. Therefore the final configuration looks as follows: p1 = a \inN, and for some r, pi equals a −(i −1) if i \leqr, and a −(i −2) otherwise. It is easy to determine a, r: since n = p1 + p2 + \cdot \cdot \cdot = (a+1)(a+2) −r, we get a(a+1) \leqn < (a+1)(a+2) , from which we uniquely find a and then r as well. The final configuration for n = 13: • • • • • • • • • • • • •