prove that $\frac{a_1+a_2+\dots+a_m}{m}\ge \frac{n+1}{2}$ Let $m$ and $n$ be positive integers. Let $a_1, a_2,\dots, a_m$ be distinct elements of $\{1, 2, \ldots, n\}$ such that whenever $a_i + a_j \le n$ for some $i,j, 1 \le i \le j \le m$, there exists $k, 1 \le k \le m$, with $a_i + a_j = a_k$. Prove that
$$\frac{a_1+a_2+\dots+a_m}{m}\ge \frac{n+1}{2}$$
Trial: I am thinking using AM$\ge$GM or $1+2+\dots+n= \frac{n(n+1)}{2}$. But unable to fully solve the problem.
 A: Let $S=\{a_1,\ldots, a_m\}$ and $a=\min S$.
For $0\le k<a$, let $$S_k=\{\,x\in S\mid x\equiv k\pmod a\,\}.$$
If $S_k$ is not empty, then because $x\in S_k$ and $a\in S$ implies $x+a\in S$ unless $x+k>n$, its elements form an arithmetic progression of step-size $a$ from $\min S\ge a$ to $\max S\ge n-a+1$. It is well-know that this implies
$$ \sum_{x\in S_k}x=|S_k|\cdot\frac{\min S+\max S}2\ge |S_k|\cdot\frac{a+n-a+1}2=|S_k|\cdot\frac{n+1}2.$$
(This inequality also holds trivially in the case that $S_k=\emptyset$).
Therefore 
$$a_1+\ldots+a_m=\sum_{x\in S} x=\sum_{k=0}^{a-1}\sum_{x\in S_k}x\ge\sum_{k=0}^{a-1}|S_k|\cdot \frac{n+1}2=|S|\cdot\frac{n+1}2$$
and after division by $|S|=m$
the original claim.
A: Using Induction
If $m=1$ then $a_1\ge \dfrac{n+1}2$
Assume for $m=m$ we have $\dfrac{a_1+a_2+\dots+a_m}{m}\ge \dfrac{n+1}{2}$
Now try to prove the inequality for $m=m+1$
We have
\begin{align*}
\frac{a_1+a_2+\dots+a_m+a_{m+1}}{m+1}&\ge \frac{\dfrac{m(n+1)}2+a_{m+1}}{m+1}\\
&\ge\frac{m}{m+1}. \frac{n+1}{2}+\frac{a_{m+1}}{m+1}\\
&\ge\frac{m}{m+1}. \frac{n+1}{2}+\frac{1}{m+1}\cdot\frac{n+1}{2} =\frac{n+1}2
\end{align*}
