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