Азиатско-Тихоокеанская математическая олимпиада, 1999 год

Последовательность $a_1$, $a_2$, $\dots$ удовлетворяет условию $a_{i + j} \leq a_i + a_j$. Докажите, что $$ {a_1} + \frac{{{a_2}}}{2} + \frac{{{a_3}}}{3} + \dots + \frac{{{a_n}}}{n} \geq {a_n}. $$

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

$$ \color{red}{(1)} : a_n\leq a_{n-1}+a_1 \leq a_{n-2}+2a_1 \leq... \leq a_{n-k}+ka_1 \leq ... \leq na_1 \Rightarrow a_1\geq \frac{a_n}{n}$$

$$ \color{red}{(2)}: a_n \leq a_{n-2}+a_2 \leq a_{n-4}+2a_2 \leq ... \leq a_{n-2k}+ka_2 \leq ... \leq \frac{n}{2} a_2 \Rightarrow \frac{a_2}{2} \geq \frac{a_n}{n}$$

$$...........................................................$$

$$ a_{n} \leq a_{n-k}+a_{k} \leq a_{n-2k}+2a_{k}\leq ... \leq \frac{n}{k} a_k\Rightarrow \frac{a_k}{k}\geq \frac{a_n}{n}$$

$$ ...........................................................$$

$$ \color{red}{(n-1)}: \frac{a_{n-1}}{n-1} \geq \frac{a_n}{n}$$

$$ \color{red}{(1)+(2)+...+(n-1):}$$

$$a_1+\frac{a_2}{2}+...+\frac{a_{n-1}}{n-1} \geq a_n \left( \underbrace{\frac{1}{n}+...+\frac{1}{n}}_{n-1} \right) =a_n \cdot \frac{n-1}{n}$$

$$a_1+\frac{a_2}{2}+...+\frac{a_{n-1}}{n-1}+\frac{a_n}{n} \geq a_n \cdot \frac{n-1}{n}+\frac{a_n}{n} =a_n$$

$$a_1+\frac{a_2}{2}+\frac{a_{3}}{3}+...+\frac{a_n}{n} \geq a_n $$