2000 IMO Problems/Problem 3

Let $n \geq 2$ be a positive integer and $\lambda$ a positive real number. Initially there are $n$ fleas on a horizontal line, not all at the same point. We define a move as choosing two fleas at some points $A$ and $B$ , with $A$ to the left of $B$ , and letting the flea from $A$ jump over the flea from $B$ to the point $C$ so that $\frac {BC}{AB} = \lambda$ .

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

Solution

The answer is $\lambda \ge \frac{1}{n-1}$ .

We change the problem be replacing the fleas by bowling balls $B_1$ , $B_2$ , \dots, $B_n$ in that order. Bowling balls aren't exactly great at jumping, so the operation now works as follows. Choose any indices $i < j$ . Then ball $B_i$ moves to $B_{i+1}$ 's location, $B_{i+1}$ moves to $B_{i+2}$ 's location, and so on; until $B_{j-1}$ moves to $B_j$ 's location, Finally, $B_j$ moves some distance at most $\lambda \cdot |B_j B_i|$ forward, but it may not pass $B_{j+1}$ .

Claim: If $\lambda < \frac{1}{n-1}$ the bowling balls have bounded movement.

Proof. Let $a_i \ge 0$ denote the initial distance between $B_i$ and $B_{i+1}$ , and let $\Delta_i$ denote the distance travelled by ball $i$ . Of course we have $\Delta_1 \le a_1 + \Delta_2$ , $\Delta_2 \le a_2 + \Delta_3$ , \dots, $\Delta_{n-1} \le a_{n-1} + \Delta_n$ by the relative ordering of the bowling balls. Finally, distance covered by $B_n$ is always $\lambda$ 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 $(n-1)\lambda > 1$ , this gives an upper bound. $\blacksquare$

Claim: When $\lambda \ge \frac{1}{n-1}$ , it suffices to always jump the leftmost flea over the rightmost flea.

Proof. If we let $x_i$ denote the distance travelled by $B_1$ in the $i$ th step, then $x_i = a_i$ for $1 \le i \le n-1$ and $x_i = \lambda(x_{i-1} + x_{i-2} + \dots + x_{i-(n-1)})$ .

In particular, if $\lambda \ge \frac{1}{n-1}$ then each $x_i$ is at least the average of the previous $n-1$ terms. So if the $a_i$ are not all zero, then $\{x_{n}, \dots, x_{2n-2}\}$ are all positive and thereafter $x_i \ge \min \left\{ x_n, \dots, x_{2n-2} \right\} > 0$ for every $i \ge 2n-1$ . So the partial sums of $x_i$ are unbounded, as desired. $\blacksquare$

Page

Toolbox

Search

2000 IMO Problems/Problem 3

Solution