2000 IMO Problems/Problem 3

Revision as of 22:43, 9 April 2021 by Math31415926535 (talk | contribs) (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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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Δnλi=1n1Δiλi=1n1((ai+ai+1++an1)+Δn)=(n1)λΔn+i=1n1iaiand 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$