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
Write ; we claim the answer is\[ \boxed{\left\{\lambda\colon \lambda \geq \frac 1N\right\}}. \]Place the points on the number line; let denote the coordinate of point . For a configuration of points , define its cap by and its score by . Notice now that we can get all the points past if and only if we can get the cap to exceed ; only if clearly holds, and for if just notice that if is past , we just reflect everything over and win. So, we just want to find so that the cap can get arbitrarily large.
Lemma 1: 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 , respectively. Then, at each point, reflect the leftmost point over the rightmost one times, until we have points all at distinct places.
Suppose our current configuration is , and let , , and write . Reflect over . Then, the configuration becomes , and the pairwise distances become , which are again all . So, at each step, we know that the cap has coordinate increasing by at least every time, so we can get the cap to be arbitrarily large.
Lemma 2: all fail.
Proof: Define the value of a configuration to be\[ V = C + \frac{\lambda S}{1-N\lambda}, \]where is the cap and is the score, respectively. We claim that the value is nonincreasing. Indeed, suppose we have a configuration , where . Suppose we reflect over with . Write , and . If the cap does not change, then clearly the score decreases, since moves closer to and the other distances do not change. Otherwise, we see that the cap increases by .
Furthermore, since we went from to , where is where 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 . 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, is indeed nonincreasing. So, if is the initial value, since always we have that\[ C\leq V \leq V_0 \]implying that indeed works, and that we cannot move all the fleas to the right of .
Thus, with both lemmas proven, we may conclude.