41st International Mathematical OlympiadIMO 2000 Problems and SolutionsTaejon, KoreaJuly 13-25, 2000 Problem 3k 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 SolutionAnswer: k >= 1/(n - 1). An elegant solution by Gerhard Woeginger is as follows: Suppose k < 1/(n - 1), so that k_{0} = 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 = 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) >= kX_{0}/(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 |