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.