# 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.

• Did you try minimizing the function of $4n-1$ variables defined by putting this all on the positive side and using the Karush-Kuhn-Tucker conditions? This is just a generalization of the case with equalities are conditions (i.e. Lagrange techniques) to inequalities. en.wikipedia.org/wiki/… Jan 31, 2015 at 4:04
• If you understand how to use these techniques it should follow straightforwardly. Otherwise I can't guess the trick at the moment. Jan 31, 2015 at 4:07
• This is problem A6 of the 44th IMO shortlist. See anhngq.files.wordpress.com/2010/07/imo-2003-shortlist.pdf for example, for a solution.
– Tim
Jan 31, 2015 at 4:32
• The preponderance of difficulty here stemmed from dealing with the superabundance of givens, especially the mysterious M.As it turned out, the inequality was no sharper than simple AM-GM! It is my opinion that it is highly unlikely that a problem as staggeringly pernicious as this one will appear on an Olympiad - at least in the foreseeable future. Jan 31, 2015 at 12:39

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