41st IMO shortlist 2000/A6 solution

41st IMO 2000 shortlist

Problem A6

a₀ < a₁ < a₂ < ... and 0 = b₀ < b₁ < b₂ < ... are sequences of real numbers such that: (1) if a_i + a_j + a_k = a_r + a_s + a_t, then (i, j, k) is a permutation of (r, s, t); and (2) a positive real x can be represented as x = a_j - a_i iff it can be represented as b_m - b_n. Prove that a_k = b_k for all k.

Solution

Notice first that x > 0 can have at most one representation as a_j - a_i. For if a_j - a_i = a_m - a_n (with j > i and m > n), then a_j + a_n + a₀ = a_m + a_i + a₀. So either m = j and n = i or m = i and n = j. The latter is not possible since j > i and m > n. So the representation is unique.

Any b_n can be written as b_n - b₀ and hence as a_i - a_j. By the remark above, this representation is unique, so let us write b_n = a_f(n) - a_g(n). Now take m > n > 0. Then b_m - b_n must be a_x - a_y for some x, y. But it is also (a_f(m) - a_g(m)) - (a_f(n) - a_g(n)), so a_f(m) + a_g(n) + a_y = a_f(n) + a_g(m) + a_x. So the f(m), g(n), y is a permutation of f(n), g(m), x. So either f(m) = f(n), g(m) = y, g(n) = x, or g(m) = g(n), f(m) = x, f(n) = y. Hence either f(m) = f(n) and g(m) ≠ g(n), or f(m) ≠ f(n) and g(m) = g(n).

Now suppose for some m > n > 0 we have f(m) = f(n) = c. Then g(m) ≠ g(n). If for some k > 0, f(k) ≠ c, then g(k) = g(m) and g(k) = g(n). Contradiction. So f(k) = c for all k > 0. Hence b_k = a_c - a_g(k). But b_k is a strictly increasing sequence, so a_g(k) is a strictly decreasing sequence. But that means g(k) is a strictly decreasing sequence. That is impossible since there are only finitely many positive integers less than g(1).

Thus we always have f(m) ≠ f(n) for m > n > 0 and hence g(m) = g(n). So b_n = a_f(n) - a_d for some d (*). Hence 0 < f(1) < f(2) < f(3) < ... .

For any m > 0, we have a_m - a₀ = b_u - b_v for some u, v. If v > 0, then we can use (*) to give a_m - a₀ = a_f(u) - a_f(v) with f(u) and f(v) > 0. But that contradicts the uniqueness of the representation a_i - a_j, so we must have v = 0. Hence a_m = b_u. So the set {a₀, a₁, ... } is contained in the set {b₀, b₁, ... }. Also a_m - a₀= a_f(u) - a_d. Hence d = 0. So for any n > 0, (*) gives b_n = a_f(n) and hence the set {b₀, b₁, ... } is contained in the set {a₀, a₁, ... }. So the sets are equal and hence a_k = b_k for all k.

41st IMO shortlist 2000