Question 13
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 which 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 obtained is unique. Describe that configuration in terms of n.
Alternative Version. A pile of 2001 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 which 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. Show that, no matter what choices are made at each stage, the final configuration obtained is unique. Describe that configuration as follows: Determine the number, $c$, of nonempty columns, and for each $i = 1, 2, \ldots, c$, determine the number of pebbles $p_i$ in column $i$, where column 1 is the leftmost column, column 2 the next to the right, and so on.
Alternative Version. A pile of 2001 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 which 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. Show that, no matter what choices are made at each stage, the final configuration obtained is unique. Describe that configuration as follows: Determine the number, $c$, of nonempty columns, and for each $i = 1, 2, \ldots, c$, determine the number of pebbles $p_i$ in column $i$, where column 1 is the leftmost column, column 2 the next to the right, and so on.