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

Write $n = N+1$; we claim the answer is\[ \boxed{\left\{\lambda\colon \lambda \geq \frac 1N\right\}}. \]Place the points on the number line; let $p$ denote the coordinate of point $P$. For a configuration $x_1\leq x_2\leq \cdots \leq x_{N+1}$ of points $X_1,X_2,\ldots, X_{N+1}$, define its cap by $x_{N+1}$ and its score by $X_1X_{N+1} + X_2X_{N+1} + \cdots + X_NX_{N+1}$. Notice now that we can get all the points past $M$ if and only if we can get the cap to exceed $m$; only if clearly holds, and for if just notice that if $X_{N+1}$ is past $M$, we just reflect everything over $X_{N+1}$ and win. So, we just want to find $\lambda$ so that the cap can get arbitrarily large.

Lemma 1: $\lambda \geq \frac 1N$ all work.

Proof: First, note that we can get a configuration in which no two fleas are at the same point. To do this, first take the leftmost point and reflect over the rightmost point. Then, we have a point strictly to the right of all other points. Suppose the points are $P_1,P_2,\ldots, P_{N+1}$, respectively. Then, at each point, reflect the leftmost point over the rightmost one $N$ times, until we have $N+1$ points all at distinct places.

Suppose our current configuration is $X_1,X_2,\ldots, X_{N+1}$, and let $d_1 = X_1X_2$, $d_2 = X_2X_3, \ldots$, and write $d = \min(d_i)>0$. Reflect $X_1$ over $X_{N+1}$. Then, the configuration becomes $X_2,X_3,\ldots, X_{N+1}, X_1'$, and the pairwise distances become $d_2,d_3,\ldots, d_N, \lambda(d_1+d_2+\cdots+d_N)$, which are again all $\geq d$. So, at each step, we know that the cap has coordinate increasing by at least $d$ every time, so we can get the cap to be arbitrarily large. $\Box$

Lemma 2: $\lambda < \frac 1N$ all fail.

Proof: Define the value $V$ of a configuration to be\[ V = C + \frac{\lambda S}{1-N\lambda}, \]where $C$ is the cap and $S$ is the score, respectively. We claim that the value is nonincreasing. Indeed, suppose we have a configuration $X_1,X_2,\ldots, X_{N+1}$, where $x_1\leq x_2\leq \cdots \leq x_{N+1}$. Suppose we reflect $X_i$ over $X_j$ with $i<j$. Write $\alpha = X_iX_j$, and $\beta =X_jX_{N+1}$. If the cap does not change, then clearly the score decreases, since $X_i$ moves closer to $X_{N+1}$ and the other distances do not change. Otherwise, we see that the cap increases by $\lambda \alpha - \beta$.

Furthermore, since we went from $X_1,X_2,\ldots, X_{N+1}$ to $X_1,X_2,\ldots, X_{i-1},X_{i+1},\ldots, X_{N+1},Q$, where $Q$ is where $X_i$ jumped to, then the score changes from\[ \sum_{k=1}^N x_{N+1}-x_k = Nx_{N+1} - \sum_{k=1}^N x_k \]to\[ \sum_{\substack{k=1\ k\neq i}}^{N+1}q - x_k = Nq - \sum_{\substack{k=1\k\neq i}}^{N+1} x_k, \]so we compute that $\Delta S = N(q-x_{N+1}) - x_{N+1}+x_i = N(\lambda\alpha-\beta) - (\alpha+\beta)$. So,\[ \Delta V = \Delta C + \frac{\lambda \Delta S}{1-N\lambda} = (\lambda\alpha-\beta) + \frac{\lambda (N(\lambda\alpha-\beta)-\alpha-\beta)}{1-N\lambda} \leq \lambda\alpha + \frac{\lambda(N\lambda-1)\alpha}{1-N\lambda} = 0. \]So, $V$ is indeed nonincreasing. So, if $V_0$ is the initial value, since $S\geq 0$ always we have that\[ C\leq V \leq V_0 \]implying that $m = V_0$ indeed works, and that we cannot move all the fleas to the right of $M$. $\Box$

Thus, with both lemmas proven, we may conclude.