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 2 of 3: Prove the paired-sum inequality

Previous step Next step

In plain words

Prove the paired-sum inequality

a_k+a_{m-k+1}\ge n+1

Detailed analysis

Suppose instead that $a_k+a_{m-k+1}\le n$ . Then the $k$ distinct sums $a_i+a_{m-k+1}$ for $1\le i\le k$ are all at most $n$ , so each belongs to the set. Every one is strictly larger than $a_{m-k+1}$ , but there are only $k-1$ elements with indices $m-k+2,\ldots,m$ , a contradiction.