Take $a_1 < a_2 < ... < a_m$. Take $k \leq (m+1)/2$. We show that $a_k + a_{m-k+1} \ge 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 $\leq 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 \leq i \leq m$, which is impossible since there are only $k-1$ available numbers in the range.

fix $n$ and use induction on $m$. If $m=1$, then $a_{1}+a_{1}$ doesn't contained in $A$ since $A$ is singalton. Thus $a_{1}+a_{1}>n$. So we get $a_{1}\geq(n+1)/2$. Assume result is true for $m-1$. Let $s=a_{1}+a_{2}+...+a_{m}$. So $s-a_{i}=a_{1}+a_{2}+...+a_{i-1}+a_{i+1}+...+a_{m}\geq\frac{n+1}{2}(m-1)$ for all $i$ by the assumption for $m-1$. $s-a_{1}\geq\frac{n+1}{2}(m-1)$ $s-a_{2}\geq\frac{n+1}{2}(m-1)$ . . . $s-a_{m}\geq\frac{n+1}{2}(m-1)$ Thus $ms-(a_{1}+a_{2}+...+a_{m})\geq\frac{n+1}{2}(m-1)(m)$. So we get $s\geq\frac{n+1}{2}(m)$. So we are done...

Re-order the set $A$ such that $a_1 < a_2 < \dots < a_m$. Now $a_i < a_j$ if and only if $i<j$. Lemma: $a_i + a_{m+1-i} \not\in A$. Assume for contradiction that it is in $A$. Then $a_i + a_{m+1-i} \le n$ which implies that for all $q$ less than or equal to $i$, it follows that $n \ge a_{m+1-i} +a_q = a_p > a_{m+1-i}$. This implies that $m \ge p > m+1-i$ and hence that there are $i-1$ possible values of $p$. However there are $i$ possible values of $q$, each of which determines a unique $p$. This is a contradiction. $\Box$ Since $a_i + a_{m+1-i} \not\in A$, it follows that $a_i + a_{m+1-i} > n$ or that $a_i + a_{m+1-i} \ge n+1$. Therefore \[(a_1 + a_m) + (a_2 + a_{m-1}) + \dots \ge \frac{m}{2}(n+1)\] \[\frac{a_1 + a_2 + \dots + a_m}{m} \ge \frac{n+1}{2} \quad \blacksquare\]

stsamster wrote: fix $n$ and use induction on $m$. If $m=1$, then $a_{1}+a_{1}$ doesn't contained in $A$ since $A$ is singalton. Thus $a_{1}+a_{1}>n$. So we get $a_{1}\geq(n+1)/2$. Assume result is true for $m-1$. Let $s=a_{1}+a_{2}+...+a_{m}$. So $s-a_{i}=a_{1}+a_{2}+...+a_{i-1}+a_{i+1}+...+a_{m}\geq\frac{n+1}{2}(m-1)$ for all $i$ by the assumption for $m-1$. $s-a_{1}\geq\frac{n+1}{2}(m-1)$ $s-a_{2}\geq\frac{n+1}{2}(m-1)$ . . . $s-a_{m}\geq\frac{n+1}{2}(m-1)$ Thus $ms-(a_{1}+a_{2}+...+a_{m})\geq\frac{n+1}{2}(m-1)(m)$. So we get $s\geq\frac{n+1}{2}(m)$. So we are done... I'm not sure this is correct ... when we remove $a_i$, the condition of the problem where there exists an $a_k$ does not necessarily hold anymore for the remaining $m$ values, and therefore we cannot apply the induction hypothesis. Am I correct?

yes you are right. Thanx for pointing it out.

I have been trying to work on proof writing skills, as I am new to olympiad math, and I would be really thankful if someone could verify the mathematical correctness of my proof and give me pointers on style.

Claim: Fix an integer $1 \leq k \leq m$. Then $a_k + a_{m - k + 1} \geq n + 1$. Proof. Suppose otherwise, and note that $a_1 < a_1 + a_1 < a_1 + a_2 < a_1 + a_3 < \dots < a_1 + a_k < a_2 + a_k < \dots < a_{m - k} + a_k < a_{m - k + 1} + a_k$ are $m + 1$ distinct positive integers less than or equal to $n$. Hence, they must be distinct members of the sequence $a_1$, $a_2$, $\dots$, $a_m$, contradiction. $\square$ Summing over all $1 \leq k \leq m$ yields \[2(a_1 + a_2 + \dots + a_m) = \sum_{k = 1}^m (a_k + a_{m - k + 1}) \geq m(n + 1),\]as desired.