header_a.gif Wolfram Research  
mainscorescontestantscompetition problemsaboutphotoIMO Facts

41st International Mathematical Olympiad

IMO 2000 Problems and Solutions

Taejon, Korea
July 13-25, 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?

Back to Competition Problems page


Answer: k >= 1/(n - 1).

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 = k1 z >= 0. So X is never decreased. But z >= k X/(n - 1) >= kX0/(n - 1) > 0. So we can move the rightmost point arbitarily 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).

Back to Competition Problems page