Пусть $A=\{a_1,a_2,\ldots,a_m\}$, $a_1\gt a_2\gt\ldots\gt a_m$. Докажем, что $a_i+a_{m+1-i}\ge n+1$ для всех $i$. Действительно, если $a_i+a_{m+1-i}\le n$ для некоторого $i$, тогда
$$
a_i\lt a_i+a_m\lt a_i+a_{m-1}\lt\ldots\lt a_i+a_{m+1-i}\le n;
$$
но все $i$ чисел $a_i+a_m$, $a_i+a_{m-1}$, $\ldots$, $a_i+a_{m+1-i}$ не могут принадлежать $A$, поскольку в $A$ существует лишь $i-1$ различных чисел $a_1\gt\ldots\gt a_{i-1}$, больших $a_i$. Отсюда следует, что $$
2(a_1+a_2+\ldots+a_m)=(a_1+a_m)+(a_2+a_{m-1})+\ldots+(a_m+a_1)\ge m(n+1),
$$
т. е.
$$
\dfrac{a_1+a_2+\ldots+a_m}m\ge\dfrac{n+1}2.
$$
