Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2001 IMO Shortlist Problems/C7

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 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$.

Solution

Note that if a column moves a pebble to the right, either the first column is still bigger or they have the same size. This means that at every point in the process, the amount of pebbles in every column decreases from left to right.

At no point during this process can there be three or more columns with the same number of pebbles. We will show this by contradiction. These columns would have to be consecutive since the amount of pebbles in each column is decreasing. Letting there be $a$ pebbles in these columns, the configuration is $(..., a, a, a, ...)$ Immediately before the first time at least three of these columns are present, The configuration must be either $(... a - 1, a, a, ...), (..., a + 1, a - 1, a, ...), (..., a, a + 1, a - 1),$ or $(..., a, a, a + 1, ...)$, none of which are legal.

Additionally, at no point during this process can there be two columns with $a$ pebbles and two with $a + 1$ pebbles for any natural number $a$. We will show this by contradiction. If so, then the configuration is $(..., a + 1, a + 1, a, a, ...)$. Immediately before, we have $(..., a, a + 1, a, a, ...), (..., a + 2, a, a, a, ...), (..., a + 1, a + 2, a - 1, a, ...), (..., a + 1, a + 1, a + 1, a - 1, ...),$ or $(..., a + 1, a + 1, a, a + 1, ...)$, none of which are legal.

Finally, we show that we can never have two columns with $a$ pebbles, two with $b$ columns, and one of every size between. We can do this by inducting on the number of pebbles on $a - b$.

Base case: $a - b = 1$. This is covered above.

Inductive step: $a - b = k -> a - b = k + 1$. Immediately before arriving at $(..., a, a, a - 1, ..., b + 1, b, b, ...),$ we must be at the position $(..., a + 1, a - 1, a - 1, ..., b + 1, b, b, ...)$ or $(..., a, a, a - 1, ..., b + 1, b + 1, b - 1, ...)$ which is impossible by our inductive hypothesis.

Thus, the final configuration must be a sequence of decreasing numbers with at most one appearing twice. There is exactly one way to represent any number in this form (start with the largest triangular number below it, add a column with the size of their difference), so there is exactly one possible final configuration.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/C7&oldid=141545"