prove that $\frac{a_1+a_2+\dots+a_m}{m}\ge \frac{n+1}{2}$

Question

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.

Answer 1

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*}

Answer 2

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.