35-я Международная Математическая OлимпиадаГонконг, Гонконг, 1994 год

Пусть $m$ и $n$ — целые положительные числа. Пусть ${{a}_{1}}$, ${{a}_{2}}$, $\ldots $, ${{a}_{m}}$ —различные элементы множества $\left\{ 1,2,\ldots ,n \right\}$ такие, что для любых индексов $i,j$, удовлетворяющих условиям $1\le i\le j\le m$ и ${{a}_{i}}+{{a}_{j}}\le n$, существует индекс $k$, $1\le k\le m$, для которого ${{a}_{i}}+{{a}_{j}}={{a}_{k}}$. Доказать, что $\dfrac{{{a}_{1}}+{{a}_{2}}+\ldots +{{a}_{m}}}{m}\ge \dfrac{n+1}{2}$.

Комментарий/решение

Админ, а ты нечего не забыл? Просто при m=3, n=2 и последовательности a = {1, 2, 1} получается контр уравнение: 1.3(3) < 1.5

m не может быть больше n, так как а[i] различные

А понял.

Claim: $a_{j}+a_{m+1-j} \geq n+1$

Prove:

Пусть $m+1-j > j$, тогда заметим что $\forall 1 \leq p \leq j-1, \exists k$ так что $a_{m+1-j}+a_p=a_k$. Заметим что все такие $a_k$ различные и их кол-во $j-1$ и они все больше $a_{m+1-j}$. То есть если $a_{j}+a_{m+1-j} \leq n$ тогда сущетсвует такой $k$ что $a_{j}+a_{m+1-j}=a_k=a_p+a_{m+1-j}$ что противоречит их различию.

Отсюда:

$(a_m+a_1)+(a_{m-1}+a_2)+… \geq \left \lceil \dfrac{m}{2} \right \rceil \cdot (n+1) \geq \dfrac{(n+1)m}{2}$