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.

Page

Toolbox

Search

2000 IMO Problems/Problem 3

Solution