Average of elements in a subset of $\{1,2,3,..,n\}$ is greater than $\frac{n+1}{2}$

Question

Consider two integers $n \ge m \ge 4$ and $A=\{a_1,a_2,...,a_m\}$ a subset of the set $\{1,2,3,...,n\}$ with the property that $$\forall a,b \in A \text{ with } a \neq b, \text{ if } a+b \le n, \text{ then } a+b \in A.$$ Prove that $$\frac{a_1+a_2+...+a_m}{m} \ge \frac{n+1}{2}.$$

Answer 1

First of all, we will order the set $A$, i.e. call $b_1$ the smallest element of $A$, $b_2$ the smallest element of $A\backslash\{b_1\}$ etcetera, up to $b_m$ to be the largest element of $A$.

Now consider the number $b_1+b_m$. If $b_1+b_m\leq n$, then $b_1+b_m\in A$. But $b_m$ was the largest element of $A$, which is a contradiction since $b_1+b_m>b_m$ ($A$ contains only strictly positive integers). So $b_1+b_m>n$. Since we are dealing with integers, this is equivalent to $b_1+b_m\geq n+1$.

Now consider $b_2+b_{m-1}$. If $b_2+b_{m-1}\leq n$, then $b_2+b_{m-1}\in A$. But since $b_1<b_2$, we then also have that $b_1+b_{m-1}\leq n$, hence $b_1+b_{m-1}\in A$. Since $b_m$ is the only element bigger than $b_{m-1}$, we find that both $b_2+b_{m-1}$ and $b_1+b_{m-1}$ must be equal to $b_m$. This is again a contradiction, so $b_2+b_{m-1}>n$. Hence $b_2+b_{m-1}\geq n+1$.

I think you can already see what we are getting at. The previous argument can be generalised further: Let $0\leq k\leq m$ be an integer, and assume $b_k+b_{m-k+1}\leq n$. Then $b_1+b_{m-k+1},b_2+b_{m-k+1},\cdots,b_k+b_{m-k+1}\in A$, hence we have $k$ (distinct) elements bigger than $b_{m-k+1}$, which is a contradiction since we can only have $m-(m-k+1)=k-1$. So $b_k+b_{m-k+1}\geq n+1$ for all $0\leq k\leq m$.

So we see that (Since $\{b_1,\cdots,b_m\}$ was just $A$ rearranged): $$2(a_1+\cdots+a_m)=2(b_1+\cdots+b_m)=(b_1+b_m)+(b_2+b_{m-1})+\cdots+(b_m+b_1)\geq m(n+1)$$ Dividing both sides by $2m$ gives: $$\frac{a_1+\cdots+a_m}{m}\geq \frac{n+1}{2} $$ Which was the desired result.