Difference between revisions of "2000 IMO Problems/Problem 3"
(Created page with "Let <math> n \geq 2</math> be a positive integer and <math> \lambda</math> a positive real number. Initially there are <math> n</math> fleas on a horizontal line, not all at t...") |
(No difference)
|
Revision as of 22:43, 9 April 2021
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
, 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.