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 $(*)$.
