IMO 1978 SL 6

Origin: FRA

Problem

Let ϕ : {1, 2, 3, . . .} \to{1, 2, 3, . . .} be injective. Prove that for all n, n  k=1 ϕ(k) k2 \geq n  k=1 k .

Solution

For fixed n and the set {ϕ(1), . . . , ϕ(n)}, there are finitely many possi- bilities for mapping ϕ to {1, . . . , n}. Suppose ϕ is the one among these for which n k=1 ϕ(k)/k2 is minimal. If i < j and ϕ(i) < ϕ(j) for some i, j \in{1, . . . , n}, define \psi as \psi(i) = ϕ(j), \psi(j) = ϕ(i), and \psi(k) = ϕ(k) for all other k. Then  ϕ(k) k2 −  \psi(k) k2

ϕ(i) i2

• ϕ(j) j2  − ϕ(i) j2
• ϕ(j) i2  = (i −j)(ϕ(j) −ϕ(i))i + j i2j2 > 0, which contradicts the assumption. This shows that ϕ(1) < \cdot \cdot \cdot < ϕ(n), and consequently ϕ(k) \geqk for all k. Hence

n  k=1 ϕ(k) k2 \geq n  k=1 k k2 = n  k=1 k .