IMO 1994

Let m and n be positive integers. Let a₁, a₂, ... , a_m be distinct elements of {1, 2, ... , n} such that whenever a_i + a_j ≤ n for some i, j (possibly the same) we have a_i + a_j = a_k for some k. Prove that:

    (a₁ + ... + a_m)/m ≥ (n + 1)/2.

Solution

Take a₁ < a₂ < ... < a_m. Take k ≤ (m+1)/2. We show that a_k + a_m-k+1 ≥ n + 1. If not, then the k distinct numbers a₁ + a_m-k+1, a₂ + a_m-k+1, ... , a_k + a_m-k+1 are all ≤ n and hence equal to some a_i. But they are all greater than a_m-k+1, so each i satisfies m-k+2 ≤ i ≤ m, which is impossible since there are only k-1 available numbers in the range.

35th IMO 1994

© John Scholes
jscholes@kalva.demon.co.uk
18 Nov 1998
Last corrected/updated 25 Aug 03