IMO 1994 Problem 1

Let $ m$ and $ n$ be two positive integers. Let $ a_1$, $ a_2$, $ \ldots$, $ a_m$ be $ m$ different numbers from the set $ \{1, 2,\ldots, n\}$ such that for any two indices $ i$ and $ j$ with $ 1\leq i \leq j \leq m$ and $ a_i +a_j \leq n$, there exists an index $ k$ such that $ a_i + a_j = a_k$. Show that $$\frac {a_1 +a_2+\dots+a_m}{m} \geq \frac {n +1}{2}.$$

=================

Proof:

The orders of $a_1,\dots,a_m$ does not matter, so assume that $a_1<a_2<\dots<a_m$. It suffices to show that for every integer $i\in[(m+1)/2,m]$, we have $$a_i+a_{m+1-i}\ge n+1.$$ If not, then the $i$ distinct numbers $a_1+a_{m+1-i},a_2+a_{m+1-i},\dots,a_i+a_{m+1-i}$, all greater than $a_{m+1-i}$, are all in set $\{a_1,\dots,a_m\}$. The set has only $i-1$ elements greater than $a_{m+1-i}$, a contradiction.