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?
Answer
k ≥ 1/(N-1).
Solution
An elegant solution by Gerhard Woeginger is as follows:
Suppose k < 1/(N-1), so that k0 = 1/k - (N - 1) > 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 = k0 z. X cannot be reduced below nil. So the total distance moved by the rightmost point is at most X0/k0, where X0 is the initial value of X.
Conversely, suppose k ≥ 1/(N-1), so that k1 = (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 = k1z ≥ 0. So X is never decreased. But z ≥ k X/(N-1) ≥ k X0/(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).
© John Scholes
jscholes@kalva.demon.co.uk
30 Aug 2000
Last corrected/updated 24 Nov 2003