IMO 2000 Problem A3 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' = k BA. For what values of k can we move the points arbitrarily far to the right by repeated moves?
k ≥ 1/(N-1). Solution An elegant solution by Gerhard Woeginger is as follows: Suppose k  0. Let X be the sum of the distances of the points from the rightmost point. If a move does not change the rightmost point, then it reduces X. If it moves the rightmost point a distance z to the right, then it reduces X by at least z/k - (N-1)z = k 0 z. X cannot be reduced below nil. So the total distance moved by the rightmost point is at most X 0 /k 0 , where X 0 is the initial value of X. Conversely, suppose k ≥ 1/(N-1), so that k 1 = (N-1) - 1/k ≥ 0. We always move the leftmost point. This has the effect of moving the rightmost point z > 0 and increasing X by (N-1)z - z/k = k 1 z ≥ 0. So X is never decreased. But z ≥ k X/(N-1) ≥ k X 0 /(N-1) > 0. So we can move the rightmost point arbitrarily far to the right (and hence all the points, since another N-1 moves will move the other points to the right of the rightmost point). 41st IMO 2000 © John Scholes jscholes@kalva.demon.co.uk 30 Aug 2000 Last corrected/updated 24 Nov 2003