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). $ 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). $$
None of the usual methods for attacking inequalities have worked on this one. Me and my friends tried it even together, and really didn't even come up to a useful lemma. I'm guessing we are all missing a fundamental insight or something, because the solution is supposed to be elementary. 
 A: For the sake of keeping this question being answered, I'm reproducing Reid's Official Solution.I have in no way answered this question myself:

Let $X=\max\{x_i\},Y=\max\{y_i\}$ . By replacing $x_i$ by $x_i'=x_i/X$, $y_i$ by $y_i'=y_i/Y$, and $z_i$ by $z_i'=z_i/\sqrt{XY}$, we may assume that $X=Y=1$. Now we will prove that
  $$M+\sum z_{2i}\ge\sum x_i+\sum y_i\tag{$*$}$$
  so
  $$\frac{M+\sum z_{2i}}{2n}\ge\frac12\left(\frac{\sum x_i}n+\frac{\sum y_i}n\right)$$
  which implies the desired result by the AM-GM inequality.
To Prove $(*)$, we will show that for any $r \ge 0$, the number of terms greater that r on the left hand side is at least the number of such terms on the right hand side. Then the $k$th largest term on the left hand side is greater than or equal to the $k$th largest term on the right hand side for each k, proving $(*)$. If r ≥ 1, then there are no terms greater than
  $r$ on the right hand side. So suppose $r < 1$. Let $A = \{1 ≤ i ≤ n | x_i > r\}$, $a = |A|$,
  $B = \{1 ≤ i ≤ n | y_i > r\}$, $b = |B|$. Since $\max\{x_1, . . . , x_n\} = \max\{y_1, . . . , y_n\} = 1$, both $a$
  and $b$ are at least $1$. Now $x_i > r$ and $y_j > r$ implies $z_{i+j} \ge
\sqrt{x_iy_j} > r$, so
  $$C=\{2\le i\le2n\mid z_i>r\}A+B=\{\alpha+\beta\mid\alpha\in A,\beta\in B\}$$
  However, we know that $|A+B|\ge|A|+|B|-1$,because if $A=\{i_1,..,i_a\}$, $i_1 < · · · < i_a$
  and $B = \{j_1, . . . , j_b\}, j_1 < · · · < j_b$, then the $a + b − 1$ numbers $i_1 + j_1, i_1 + j_2, . . . , i_1 + j_b$,
  $i_2 +j_b, . . . , i_a +j_b$ are all distinct and belong to $A+B$. Hence $|C| ≥ a+b−1$. In particular,
  $|C| ≥ 1 so z_k > r$ for some $k$. Then $M > r$, so the left hand side of $(*)$ has at least $a + b$
  terms greater than $r$. Since $a + b$ is the number of terms greater than $r$ on the right hand
  side, we have proved $(*)$.

