2003 IMO SL #A6

Let $n$ be a positive integer and let $(x_1,\ldots,x_n)$, $(y_1,\ldots,y_n)$ be two sequences of positive real numbers. Suppose $(z_2,\ldots,z_{2n})$ is a sequence of positive real numbers such that $z_{i+j}^2 \geq x_iy_j$ for all $1\le i,j \leq n$. Let $M=\max\{z_2,\ldots,z_{2n}\}$. Prove that\[ \left( \frac{M+z_2+\dots+z_{2n}}{2n} \right)^2 \ge \left( \frac{x_1+\dots+x_n}{n} \right) \left( \frac{y_1+\dots+y_n}{n} \right). \]

Multiplying both sides by $4n^2$, we see that it suffices to prove \[(M + z_2 + \ldots + z_{2n})^2 \geq 4(x_1 + \ldots + x_n)(y_1 + \ldots y_n)\]or

$$(M+z_2+\cdots+z_{2n}) \ge 2\sqrt{(x_1+\cdots+x_n)(y_1+\cdots+y_n)}.$$

Also, by the AM-GM inequality, we know that $$(x_1+\cdots+x_n)+(y_1+\cdots+y_n) \ge 2 \sqrt{(x_1+\cdots+x_n)(y_1+\cdots+y_n)},$$

so it is enough to prove $$(M+z_2+\cdots+z_{2n}) \ge (x_1+\cdots+x_n)+(y_1+\cdots+y_n). \qquad  (\star)$$There seems no usual method to prove this inequality, so we adopt unusual methods. 

WLOG, let $\text{max}\{x_1,x_2, \dots x_n\}=\text{max}\{y_1,y_2, \dots y_n\}=1 .$

Note that it suffices to prove that for any real number $0 \le r \le 1$, we will have that the number of terms at least $r$ on the LHS of $(\star)$ is greater than or equal to that of the RHS of $(\star)$. To prove this, consider the sets $\mathcal{S}_1=\{1 \le i \le n, x_i \ge r\}$ and $\mathcal{S}_2=\{1 \le i \le n, y_i \ge r\}$. Then, the RHS of $(\star)$ has $|\mathcal{S}_1|+|\mathcal{S}_2|$ terms at least $r$. Now, if $x_i, y_i \ge r$, then we will have $z_{i+j} \ge \sqrt{x_iy_i}\geq r$, and so the LHS has at least $|\mathcal{S}_1+\mathcal{S}_2|+1$ terms at least $r$, where the $1$ accounts for $M$. 

Hence, now it only remains to show $$|\mathcal{S}_1+\mathcal{S}_2| \geq |\mathcal{S}_1| + |\mathcal{S}_2| - 1,$$which is well-known, and can be easily proven as well.