IMO 2000 SL A5

Origin: BLR | Category: Algebra

Problem

Let n \geq2 be a positive integer and \lambda a positive real number. Initially there are n fleas on a horizontal line, not all at the same point. We define a move of choosing two fleas at some points A and B, with A to the left of B, and letting the flea from A jump over the flea from B to the point C such that BC/AB = \lambda. Determine all values of \lambda such that for any point M on the line and for any initial position of the n fleas, there exists a sequence of moves that will take them all to the position right of M.

Solution

We claim that for \lambda \geq n−1 we can take all fleas as far to the right as we want. In every turn we choose the leftmost flea and let it jump over the rightmost one. Let d and \delta denote the maximal and the minimal distances between two fleas at some moment. Clearly, d \geq(n −1)\delta. After the leftmost flea jumps over the rightmost one, the minimal distance does not decrease, because \lambdad \geq\delta. However, the position of the leftmost flea moved to the right by at least \delta, and consequently we can move the fleas arbitrarily far to the right after a finite number of moves. Suppose now that \lambda < n−1. Under this assumption we shall prove that there is a number M that cannot be reached by any flea. Let us assign to each flea the coordinate on the real axis in which it is settled. Denote by sk the sum of all the numbers in the kth step, and by wk the coordinate of the rightmost flea. Clearly, sk \leqnwk. We claim that the sequence wk is bounded. In the (k+1)th move let a flea A jump over B, landing at C, and let a, b, c be their respective coordinates. We have sk+1 −sk = c −a. Then by the given rule, \lambda(b −a) = c −b = sk+1 −sk + a −b, which implies sk+1 −sk = (1+\lambda)(b−a) = 1+\lambda \lambda (c−b). Hence sk+1 −sk \geq1+\lambda \lambda (wk+1 −wk). Summing up these inequalities for k = 0, . . . , n −1 yields sn −s0 \geq1+\lambda \lambda (wn −w0). Now using sn \leqnwn we conclude that 1 + \lambda \lambda −n  wn \leq1 + \lambda \lambda w0 −s0. Since 1+\lambda \lambda −n > 0, this proves the result.