IMO 1978/B2 solution

IMO 1978

Problem B2

{a_k} is a sequence of distinct positive integers. Prove that for all positive integers n, ∑₁ⁿ a_k/k² ≥ ∑₁ⁿ 1/k.

Solution

We use the general rearrangement result: given b₁ ≥ b₂ ≥ ... ≥ b_n, and c₁ ≤ c₂ ≤ ... ≤ c_n, if {a_i} is a permutation of {c_i}, then ∑ a_ib_i ≥ ∑ c_ib_i. To prove it, suppose that i < j, but a_i > a_j. Then interchanging a_i and a_j does not increase the sum, because (a_i - a_j)(b_i - b_j) ≥ 0, and hence a_ib_i + a_jb_j ≥ a_jb_i + a_ib_j. By a series of such interchanges we transform {a_i} into {c_i} (for example, first swap c₁ into first place, then c₂ into second place and so on).

Hence we do not increase the sum by permuting {a_i} so that it is in increasing order. But now we have a_i > i, so we do not increase the sum by replacing a_i by i and that gives the sum from 1 to n of 1/k.

Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

20th IMO 1978