Problem 1

Let

a_1,\ldots,a_m

be distinct elements of

\{1,\ldots,n\}

such that whenever

a_i+a_j\le n

(with

i\le j

), the sum is also one of the

a_k

. Prove

\frac{a_1+\cdots+a_m}{m}\ge\frac{n+1}{2}

Step 3 of 3: Sum the pairs

Previous step Next step

In plain words

Sum the pairs

2\sum_{i=1}^m a_i\ge m(n+1)

Detailed analysis

Sum $a_k+a_{m-k+1}\ge n+1$ over $k=1,\ldots,\lfloor(m+1)/2\rfloor$ , counting the central inequality once when $m$ is odd. Equivalently, summing all paired inequalities gives $2\sum_{i=1}^m a_i\ge m(n+1)$ . Divide by $2m$ to obtain $\frac{a_1+\cdots+a_m}{m}\ge\frac{n+1}{2}$ .