IMO 2000 · Problem 3

\(k\) is a positive real. \(N\) is an integer greater than 1. \(N\) points are placed on a line, not all coincident. A move is carried out as follows. Pick any two points \(A\) and \(B\) which are not coincident. Suppose that \(A\) lies to the right of \(B\). Replace \(B\) by another point \(B'\) to the right of \(A\) such that \(AB' = kBA\). For what values of \(k\) can we move the points arbitrarily far to the right by repeated moves?

Restatement of the problem, as in John Scholes' Kalva archive; the official wording is in the official problem paper. Official problem paper (PDF)

Answer

\[ \boxed{k\ge \frac{1}{N-1}}. \]

Solution

Give the line a coordinate increasing to the right. For any configuration, let \(M\) be its maximum coordinate and \(S\) the sum of its \(N\) coordinates, counting coincident points separately.

Impossibility when \(k<1/(N-1)\). Define \[ F=(1+k)M-kS. \] Consider any legal move using coordinates \(b<a\), and put \(d=a-b>0\). The new coordinate is \[ b'=a+kd, \] so the sum increases by \((1+k)d\). Since \(a\le M\), the maximum increases by at most \(kd\). Consequently, \[ F_{\mathrm{new}}-F \le (1+k)kd-k(1+k)d=0. \] Thus \(F\) never increases.

On the other hand, \(S\le NM\), and hence \[ F\ge (1+k-kN)M=\bigl(1-(N-1)k\bigr)M. \] Writing \(F_0\) for the initial value, we obtain \[ M\le \frac{F_0}{1-(N-1)k}. \] The denominator is positive, so this is a fixed upper bound for every point under every sequence of moves. The required motion is therefore impossible.

Construction when \(k\ge1/(N-1)\). At each step, choose a leftmost point and move it across a rightmost point. Write \(m\) for the current minimum and \(D=M-m\) for the diameter. The new point has coordinate \[ M+kD. \] Initially \(D>0\), and each such move places a point strictly beyond all the others, so \(D>0\) remains true and the strategy can continue indefinitely.

Consider \[ T=NM-S=\sum_{i=1}^{N}(M-x_i). \] Its initial value \(T_0\) is positive because the initial points are not all coincident. Under our chosen move, \[ M_{\mathrm{new}}=M+kD,\qquad S_{\mathrm{new}}=S+(1+k)D. \] Therefore \[ T_{\mathrm{new}} =T+\bigl((N-1)k-1\bigr)D \ge T. \] In particular, \(T\ge T_0>0\) throughout.

At least one summand in \(T\) is zero, and every other summand is at most \(D\). Thus \[ T\le (N-1)D, \qquad D\ge \frac{T_0}{N-1}. \] Every move consequently increases the maximum by at least \[ kD\ge \frac{kT_0}{N-1}>0. \] Hence the maximum tends to \(+\infty\).

Finally, fix any target coordinate \(R\). Continue until the maximum exceeds \(R\), and denote that maximum by \(M_*\). During the next \(N\) moves, every newly placed point lies strictly beyond \(M_*\). As long as any point from the configuration at that moment remains unmoved, its coordinate is at most \(M_*\), so a leftmost point must be one of those unmoved points. Thus these \(N\) moves move every point beyond \(M_*>R\).

This proves the claim for all initial configurations, including those with coincident points, and includes the boundary value \(k=1/(N-1)\).

The solution was checked against Evan Chen's published IMO solution notes.