Let m and n be positive integers. Let a_{1}, a_{2}, ... , 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_{1} + ... + a_{m})/m ≥ (n + 1)/2.

**Solution**

Take a_{1} < a_{2} < ... < 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_{1} + a_{m-k+1}, a_{2} + 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.

© John Scholes

jscholes@kalva.demon.co.uk

18 Nov 1998

Last corrected/updated 25 Aug 03