MathLabs

Problem 1

Let a1,…,ama_1,\ldots,a_m be distinct elements of {1,…,n}\{1,\ldots,n\} such that whenever ai+aj≤na_i+a_j\le n (with i≤ji\le j), the sum is also one of the aka_k. Prove a1+⋯+amm≥n+12\frac{a_1+\cdots+a_m}{m}\ge\frac{n+1}{2}.
Step 1 of 3: Sort the elements
Previous stepNext step
In plain words

Sort the elements

a1<a2<⋯<ama_1<a_2<\cdots<a_m
Detailed analysis

Relabel the set so that a1<a2<⋯<ama_1<a_2<\cdots<a_m. We prove the key inequality for k≤(m+1)/2k\le(m+1)/2.