# 2000 IMO Problems/Problem 3

Let be a positive integer and a positive real number. Initially there are fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas at some points and , with to the left of , and letting the flea from jump over the flea from to the point so that .

Determine all values of such that, for any point on the line and for any initial position of the fleas, there exists a sequence of moves that will take them all to the position right of .

## Solution

The answer is .

We change the problem be replacing the fleas by bowling balls , , \dots, in that order. Bowling balls aren't exactly great at jumping, so the operation now works as follows. Choose any indices . Then ball moves to 's location, moves to 's location, and so on; until moves to 's location, Finally, moves some distance at most forward, but it may not pass .

Claim: If the bowling balls have bounded movement.

Proof. Let denote the initial distance between and , and let denote the distance travelled by ball . Of course we have , , \dots, by the relative ordering of the bowling balls. Finally, distance covered by is always times distance travelled by other bowling balls, so\begin{align*} \Delta_n &\le \lambda \sum_{i=1}^{n-1} \Delta_i \le \lambda \sum_{i=1}^{n-1} \left( \left( a_i + a_{i+1} + \dots + a_{n-1} \right) + \Delta_n \right) \\ &= (n-1)\lambda \cdot \Delta_n + \sum_{i=1}^{n-1} i a_i \end{align*}and since , this gives an upper bound.

Claim: When , it suffices to always jump the leftmost flea over the rightmost flea.

Proof. If we let denote the distance travelled by in the th step, then for and .

In particular, if then each is at least the average of the previous terms. So if the are not all zero, then are all positive and thereafter for every . So the partial sums of are unbounded, as desired.