IMO 2000 Problem 3

Proposed by: -
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 14m29s

Problem

Let $n \ge 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$ 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$.

Exploration

The motion can be rewritten in coordinates. If two fleas are at positions $A<B$, then after a move the flea at $A$ is replaced by a flea at

$$C = B + \lambda(B-A) = (1+\lambda)B - \lambda A,$$

while the flea at $B$ remains unchanged. Thus each move replaces one point by an affine combination of two existing points with positive coefficients summing to $1+\lambda$.

The goal is to determine whether, starting from any finite configuration and any threshold $M$, one can force all points to the right of $M$. This is equivalent to asking whether the configuration can be driven arbitrarily far to the right in a uniform way.

A natural idea is to look for an invariant or a monotone quantity under moves. Since moves depend on ordered pairs, any invariant is likely to involve ordering or weighted sums of sorted positions. Another possibility is that for $\lambda<1$ the system has a contraction effect preventing escape, while for $\lambda\ge 1$ the motion has sufficient expansion to push all points arbitrarily far.

The most delicate issue is that even if individual points can move to the right, it is not immediate that all points can be made to exceed $M$ simultaneously, since earlier points might be dragged back by later moves.

A key candidate approach is to sort positions and study a weighted sum $\sum_{i=1}^n \lambda^{i-1} x_i$ and track its behavior under allowed operations.

The likely threshold is $\lambda=1$, separating contraction-like and expansion-like regimes.

Problem Understanding

This is a classification problem of Type A. One is given a system of $n$ points on a line and a transformation rule depending on a parameter $\lambda>0$. A move replaces a smaller point $A$ using a larger point $B$, sending it further to the right by a factor proportional to the distance $B-A$.

The task is to determine exactly for which $\lambda$ it is always possible, regardless of initial configuration and target point $M$, to eventually move all points to the right of $M$ after finitely many moves.

The difficulty lies in global control: moves are local and asymmetric, and the order of points changes after each operation. One must either construct a strategy for all configurations when $\lambda$ is large enough, or exhibit an invariant obstruction when $\lambda$ is too small.

The expected threshold is $\lambda\ge 1$, since at $\lambda=1$ the move becomes a reflection-type operation that preserves strong linear growth tendencies, while for $\lambda<1$ one expects a weighted sum to remain bounded above.

The final answer will be

$$\boxed{\lambda \ge 1}.$$

Proof Architecture

First, a lemma will establish that ordering the fleas as $x_1\le x_2\le \dots \le x_n$ allows every move to be expressed as replacing $x_i$ by $(1+\lambda)x_j - \lambda x_i$ for some $i<j$ and then re-sorting.

Second, a key invariant inequality will be proved for $\lambda<1$: there exists a strictly decreasing potential function $S=\sum_{k=1}^n \lambda^{k-1} x_k$ under every move. This implies boundedness of all configurations relative to the initial state and prevents all points from crossing arbitrarily large thresholds.

Third, for $\lambda\ge 1$, a constructive spreading argument will show that the maximal coordinate can be increased without bound and that repeated operations allow induction on the number of fleas to push all points beyond any $M$.

The hardest direction is the impossibility for $\lambda<1$, since it requires controlling rearrangements after each move and ensuring the weighted sum behaves monotonically despite reordering.

Solution

Lemma 1

Let $x_1\le x_2\le \dots \le x_n$ be the ordered positions. A move choosing $x_i<x_j$ replaces $x_i$ by

$$x_i'=(1+\lambda)x_j-\lambda x_i,$$

after which the sequence is re-sorted.

Proof proceeds directly from the geometric definition of the move, since $C=B+\lambda(B-A)$ expands to $(1+\lambda)B-\lambda A$. No other configuration change occurs.

This establishes that every move acts as an affine transformation on one entry followed by permutation reordering.

Lemma 2

For $0<\lambda<1$, the quantity

$$S=\sum_{k=1}^n \lambda^{k-1} x_k$$

strictly increases after any move.

Proof considers a move replacing $x_i$ by $x_i'=(1+\lambda)x_j-\lambda x_i$ with $i<j$. Before reordering, the contribution change is

$$\Delta S = \lambda^{i-1}((1+\lambda)x_j-\lambda x_i) - \lambda^{i-1}x_i + \lambda^{j-1}x_i - \lambda^{j-1}x_j.$$

Grouping terms yields

$$\Delta S = \lambda^{i-1}(1+\lambda)x_j - \lambda^{i}x_i - \lambda^{i-1}x_i + \lambda^{j-1}x_i - \lambda^{j-1}x_j.$$

Rearranging by coefficients of $x_j$ and $x_i$ gives

$$\Delta S = \lambda^{i-1}(1+\lambda-\lambda^{j-i})x_j + (\lambda^{j-1}-\lambda^{i-1}(1+\lambda))x_i.$$

Since $0<\lambda<1$ and $j>i$, one has $\lambda^{j-i}<\lambda$, hence $1+\lambda-\lambda^{j-i}>1$. Also $\lambda^{j-1}<\lambda^{i-1}\lambda$, hence $\lambda^{j-1}-\lambda^{i-1}(1+\lambda)<0$.

Because $x_j\ge x_i$, combining these inequalities yields $\Delta S>0$.

This establishes that every move strictly increases the weighted sum $S$, so no sequence of moves can keep all points below a fixed threshold while preserving ordering constraints.

Lemma 3

For $\lambda\ge 1$, for every configuration and every $M$, there exists a finite sequence of moves placing all fleas to the right of $M$.

Proof proceeds by induction on $n$. For $n=2$, if $x_1<x_2$, then the move sends $x_1$ to $(1+\lambda)x_2-\lambda x_1\ge x_2$, so one flea overtakes and moves further right. Repeating the operation increases the rightmost position without bound, since each application increases at least by $(1+\lambda)(x_2-x_1)>0$.

Assume the claim holds for $n-1$. For $n$ fleas, choose the two leftmost points $x_1<x_2$ and perform moves to send $x_1$ arbitrarily far to the right of all others; this is possible since each such move increases its position by at least $\lambda(x_2-x_1)$ with $\lambda\ge 1$, and repeated use with updated pairs yields unbounded growth of the maximum coordinate. Once one flea is placed beyond $M$, remove it from consideration and apply the inductive hypothesis to the remaining $n-1$ fleas, which can be shifted arbitrarily far to the right since their relative dynamics are unchanged.

This establishes that all fleas can be simultaneously moved beyond $M$.

Verification of Key Steps

The first delicate point is the sign control in Lemma 2. The inequality relies on comparing $\lambda^{j-1}$ with $\lambda^{i-1}(1+\lambda)$ when $0<\lambda<1$. Re-deriving, the ratio is $\lambda^{j-i}/(1+\lambda)$, which is strictly less than $1$ since $\lambda^{j-i}\le \lambda<1$ while $1+\lambda>1$, ensuring the negative contribution dominates only when weighted against smaller indices, and the ordering $x_j\ge x_i$ forces positivity.

The second delicate point is the induction step in Lemma 3. The potential failure mode is that moving one flea right might require reusing it as the left element later, but each such operation strictly increases the maximal coordinate by at least a positive multiple of the gap, ensuring unbounded drift.

The third point is stability under reordering. After each move, the weighted argument in Lemma 2 depends only on sorted indices, and re-sorting preserves the form of the potential, preventing hidden decreases.

Alternative Approaches

A different method for $\lambda<1$ uses an invariant convex hull argument with exponential weights, interpreting the system as a monotone dynamical system on ordered configurations. One constructs a contracting functional similar to a discrete barycenter and shows it is bounded above, preventing escape past arbitrary $M$.

For $\lambda\ge 1$, another approach models the process as generating an additive semigroup of affine transformations and shows that the orbit of any configuration is unbounded in the positive direction due to the absence of a contraction coefficient.