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.