I'm curious who can share with us a solution. This is the most unconventional and hard inequality I have ever seen. Absolutely impossible. As far as I heard, no contestant in Mathlinks Contest managed to do it. Is there anyone who can supply a proof?

I have thought on this proble nearly 1 hour and I obtained nothing. It's impossible. Do you know which country sent this problem. :(

Ha, ha, I like that with one hour. So, should I understand that every inequality except this one, you managed to prove it in one hour? Boy, you really are tough! I spent two days on this problem and couldn't find anything. But I'm not the only one, since I heard that none from the leaders in OIM could solve it. This problem is created by Reid Barton. I think it says something, right?

harazi wrote: Ha, ha, I like that with one hour. So, should I understand that every inequality except this one, you managed to prove it in one hour? Boy, you really are tough! I spent two days on this problem and couldn't find anything. But I'm not the only one, since I heard that none from the leaders in OIM could solve it. This problem is created by Reid Barton. I think it says something, right? Who is Reid Barton?

One of the best IMO contestants ever - he scored four gold medals I think, and got full marks at IMO 2001.

I have proved following inequality: \[ S^2\geq (x_1+x_2+\dots x_n)(y_1+y_2+\dots+y_n),\] where $S=\max\limits_{i=1,\dots,n}(z_{i+1}+z_{i+1}+\dots z_{i+n})$. Did anybody prove other similar inequalities?

I think this inequality is a kind of improvement of classical Cotlar-Stein inequality: Lemma (Cotlar, Stein). Let $z_i\geq 0$, $i\in\mathbb{Z}$, and $S=\sum\limits_{-\infty}^{+\infty}z_i<+\infty$. Let $T_1,\,T_2,\,\dots,\,T_n$ be linear continuous operators in Hilbert space $H$, $||T_i^*T_j||\leq z_{i-j}^2$ and $||T_iT_j^*||\leq z_{i-j}^2$ $\forall\,i,j\in\{1,2,\dots,n\}$. Then $||T_1+T_2+\dots+T_n||\leq S$. Unfortunately in our case using of this inequality gives too bad estimation, but its technique brings us to inequality from my previous post.

The official solution is this (im just copying from the booklet ): and its really nice: Let X = max (x1,x2 ... x(n)), and Y = max (y1,y2 ... y(n)). By replacing with x(i)'=x(i)/X, and y(i)'=y(i)/Y and z(i) by z(i)'=z(i)/sqrt XY, we may assume X=Y=1. Now we prove the following: M + z2 + ... + z(2n) >= x1 + x2 ... + x(n) + y1 + y2 ... + y(n) ... (*) from which the result follows with am-gm. to prove (*) we will show that for any r>=0, the number of terms greater than r on the left hand side is at leas 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 number of such terms on the right hand side for each k proving (*) (really wierd ..). 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 { x1, x2, ... x(n)} = max {y1, y2 ... y(n)} = 1, both a and b are at least 1. Now x(i) > r and y(j) > r implies z(i+j) >= sqrt (x(i)*y(j)) > r, so C = {2 <= i <= 2n | z(i) > r} is at least as large as A+B = {x+y | x in A, y in B}. However we know |A+B| >= |A| + |B| - 1 because if A={i1,i2 .. i(a)}, i1<i2 .. <i(a) and B ={j1,j2 .. j(b)}, j1<j2 ... <j(b) then the a+b-1 numbers i1+j1, i1+j2 ... i1+jb, i2+jb, ... 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 proven (*).

Quote: to prove (*) we will show that for any r>=0, the number of terms greater than 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 number of such terms on the right hand side for each k proving (*) (really wierd ..). I really don't understand this step. Has anyone studied and understood it ? Thank you very much.

Hi Manlio! manlio wrote: Quote: to prove (*) we will show that for any r>=0, the number of terms greater than 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 number of such terms on the right hand side for each k proving (*) (really wierd ..). I really don't understand this step. I'm sorry for the belated reply, I also had my troubles with this passage. In fact, it is a really ingenious argument but I don't understand how Vinoth_90_2004 justifies it. Just let me tell you how I justify it: The crux here is the following lemma: Lemma 1. Let $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$ be positive real numbers. Assume that for every positive real number r, the number of all i such that $a_i > r$ is greater or equal to the number of all i such that $b_i > r$. Then, $a_1 + a_2 + ... + a_n \geq b_1 + b_2 + ... + b_n$. Proof. For any positive real number r, let the A(r) denote the number of all i such that $a_i > r$, and let B(r) denote the number of all i such that $b_i > r$. Then, we know that $A\left( r\right) \geq B\left( r\right)$ holds for all $r \geq 0$. Moreover, the functions A(r) and B(r) are piecewisely constant functions, and hence we can integrate them. (Actually, I will integrate them out of laziness. The proof can be rewritten in a completely elementary form, since instead of integrating piecewisely constant functions, you can just write down a sum of finitely many rectangle areas.) Remember that the numbers $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$ are all positive, and we can interchange the $a_1$, $a_2$, ..., $a_n$ arbitrarily and interchange the $b_1$, $b_2$, ..., $b_n$ arbitrarily without changing everything in the assertion of the theorem. Hence, we can WLOG assume that $0 < a_1 \leq a_2 \leq ... \leq a_n$ and $0 < b_1 \leq b_2 \leq ... \leq b_n$. Finally, there obviously exists a positive number q which is greater than all of the numbers $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$. Then, we can easily see that \int\limits_0^q A\left( r\right) dr = a_1 + a_2 + ... + a_n and \int\limits_0^q B\left( r\right) dr = b_1 + b_2 + ... + b_n. Now, since we have $A\left( r\right) \geq B\left( r\right)$ for all $r \geq 0$, we also get \int\limits_0^q A\left( r\right) dr \geq \int\limits_0^q B\left( r\right) dr, so that $a_1 + a_2 + ... + a_n \geq b_1 + b_2 + ... + b_n$. This proves Lemma 1. Oh yes, I really wonder how Vinoth_90_2004's proof (or, more exactly, the proof from the Shortlist booklet) goes. I hope it is simpler than mine... Darij

darij grinberg wrote: Lemma 1. Let $a_1$, $a_2$, ..., $a_n$, $b_1$, $b_2$, ..., $b_n$ be positive real numbers. Assume that for every positive real number r, the number of all i such that $a_i > r$ is greater or equal to the number of all i such that $b_i > r$. Then, $a_1 + a_2 + ... + a_n \geq b_1 + b_2 + ... + b_n$. [...] \int\limits_0^q A\left( r\right) dr \geq \int\limits_0^q B\left( r\right) dr, Oh yes, I really wonder how Vinoth_90_2004's proof (or, more exactly, the proof from the Shortlist booklet) goes. I hope it is simpler than mine... Darij Very nice! In a private message to manlio, I actually proved that $a_k\geq b_k$ if both sequences are sorted in increasing order. Is it possible to explain this using integrals? PS. I can't copy my message here because I can't see the quote in the Sentbox and I don't want to re-type it, maybe manlio can see the quote from his Inbox.

fuzzylogic wrote: I actually proved that $a_k\geq b_k$ if both sequences are sorted in increasing order. Oh yes. This was the cook! I must have been too blind to note this simple argument. Especially if we use my notations A(r) and B(r) and my WLOG assumption $0 < a_1 \leq a_2 \leq ... \leq a_n$ and $0 < b_1 \leq b_2 \leq ... \leq b_n$, this argument becomes trivial: For every k, we have $A\left( a_k \right) \leq n-k$. This is because $A\left( a_k \right) $ is the number of all i such that $a_i > a_k$, and actually there are at most n - k such numbers i (in fact, in the usual case, there are exactly n - k such numbers i, but if $a_k = a_{k+1}$, this number becomes smaller). Now we have by assumption $A\left( r\right) \geq B\left( r\right)$ for every positive r, hence we have particularly $A\left( a_k \right) \geq B\left( a_k \right) $. Together with $A\left( a_k \right) \leq n-k$, this yields $B\left( a_k\right) \leq n-k$. Now, if we would have $a_k < b_k$, then we also would have $a_k < b_k \leq b_{k+1} \leq ... \leq b_n$, so we would already have at least n - k + 1 numbers i such that $b_i > a_k$. Hence, the value $B\left( a_k\right) $ would be at least n - k + 1. But this contradicts $B\left( a_k\right) \leq n-k$. Hence we can never have $a_k < b_k$. Thus, we must have $a_k \geq b_k$ for every k. Summing up, this yields $a_1 + a_2 + ... + a_n \geq b_1 + b_2 + ... + b_n$. This proves Lemma 1. Yes, Fuzzylogic, this is not only a proof which is much simpler than mine; now I also understand that this is exactly the same argument Vinoth_90_2004 gave! But after all, what I did was a pretty neat exercise on applying integral calculus, wasn't it? Darij

This inequality is a particular case of Prekopa-Leindler inequality. It says that if we take the function $ h(t) = \sup \{f(x)g(y) \mid x+y=t\} $ then $\int_0^{\infty} h(t)dt$ is at least $ 2\sqrt{\int_0^{\infty} f^2(x) dx} \cdot \sqrt{\int_0^{\infty} g^2(x)dx} $. This explains the official solution.

This is the proof of Fuzzylogic. fuzzylogic wrote: Quote: to prove (*) we will show that for any r>=0, the number of terms greater than 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 number of such terms on the right hand side for each k proving (*) (really wierd ..). I think I understand the logic. Let me try to rephrase it as a lemma as follows: Lemma Let $0< a_1\le a_2 \le \cdots \le a_m$ and $0 < b_1 \le b_2 \le \cdots \le b_m$ be two increasingly sorted sequences of positive reals. For any real $r$, define $A_r = \{i \,|\, a_i > r\}$ and $B_r = \{i \,|\, b_i > r\}$. Assume that $|A_r| \geq |B_r|$ for any $r\ge 0$, then $a_k \ge b_k$ for any $1\le k \le m$. Proof: (by contradiction) Suppose $a_k < b_k$ for some $1\le k \le m$. Pick any real $r$ such that $a_k<r < b_k$, then $A_r \subseteq \{i \,|\, k+1\le i \le m\}$, so $|A_r| \le m-k$. On the other hand, $B_r \supseteq \{i \,|\, k \le i \le m\}$, so $|B_r| \ge m-k+1$. A contradiction. This proves the lemma. Note: It follows immediately from the lemma that $a_1+ a_2 + \cdots + a_m \geq b_1 +b_2 + \cdots + b_m$. Fuzzylogic proof is very nice as it uses a contradiction argument. Darij proof is very nice as it is simple to understand. Thank you very much to both of you to have made clear to me this hard step.

16 year bump We make some adjustments to start with . WLOG $\operatorname{max}\{x_1,x_2, \dots x_n\}=\operatorname{max}\{y_1,y_2, \dots y_n\}=1 .$ Next assume WLOG that the $z_i$'s are as small as possible . In other words , assume $z_{i+j}^2 = \operatorname{max}_{i+j=\text{constant}} (x_i \cdot y_j)$ . Hence , $M=1$ . Now we claim that the following inequality holds true . Claim : $$M+ \sum_{k=2}^{2n}z_k \geq \sum_{k=1}^{n}x_k + \sum_{k=1}^{n}y_k$$. Proof : We basically need to show that for all reals $r \in (0,1)$ , the following inequality holds : $($# terms on LHS $\geq r)$ $\geq$ $($# terms on RHS $\geq r)$ Define sets$$X = \{i : x_i \geq r\}$$$$Y = \{j : y_j \geq r\}$$Note that $ z_{i+j}^2 \geq x_iy_j \implies$ $($#terms on LHS $\geq r)$$ \geq |X+Y|+1 .$ (The extra +1 term is due to the extra $M=1$) . Hence we just need $|X+Y|+1 \geq |X|+|Y|$ , which is a well known result . We are done by AM-GM

Remark: Similar to above proofs, but shows why $|X + Y| + 1 \geq |X| + |Y|$ is well known. Pick all $z_k$ to be the least possible; that is, for each $k$, let $z_k = \max_{i + j = k} \sqrt{x_iy_j}$. Notice that since this inequality is homogeneous, we may actually scale $\max{(x_1, \ldots , x_n)}$ and $\max{(y_1, \ldots , y_n)}$ both to $1$, so $M = 1$. We wish to prove that\[(M + z_2 + \ldots + z_{2n})^2 \geq 4(x_1 + \ldots + x_n)(y_1 + \ldots y_n)\]but since $(x_1 + \ldots x_n) + (y_1 + \ldots + y_n) \geq 2\sqrt{(x_1 + \ldots + x_n)(y_1 + \ldots y_n)}$ it suffices to show that\[M + z_2 + \ldots + z_{2n} \geq \sum x_i + \sum y_i.\]We will do this by showing that for every real $r \in [0, 1]$, the number of terms in the LHS $\geq r$ is at least the number of terms in the RHS $\geq r$. Let $S$ be the set of indices $s$ for which $x_s \geq r$ and $T$ be the set of indices $t$ for which $y_t \geq r$. Clearly the RHS has $|S| + |T|$ terms $\geq r$. The LHS has at least $|S + T| + 1$ terms $\geq r$ where $S + T$ is the set of reals of the form $x_i + y_j$ for $i \in S$ and $j \in T$. So it remains to prove that\[|S + T| \geq |S| + |T| - 1\]for all sets $S, T$. We just need to find $|S| + |T| - 1$ distinct elements in $S + T$. Write elements of $S$ and $T$ as $a_1 < \ldots < a_{|S|}$ and $b_1 < \ldots < b_{|T|}$ in increasing order. WLOG $|S| \leq |T|$. First, consider the sums\[\{x_1 + y_1, y_1 + x_2, x_2 + y_2, \ldots , y_{|S| - 1} + x_{|S|}, x_{|S|} + y_{|S|}\}\]which are clearly all distinct and increasing. There are $2|S| - 1$ of them. Next, we just need to consider\[\{x_{|S|} + y_{|S| +1}, \ldots , x_{|S|} + y_{|T|}\}\]which again are clearly increasing and $x_{|S|} + y_{|S| +1} > x_{|S|} + y_{|S|}$. There are $|T| - |S|$ of them. All of these terms must be distinct because they are arranged in increasing order, hence this is a total of $(2|S| - 1) + (|T| - |S|) = |S| + |T| - 1$ terms, as desired. Tracking back we may see that our original inequality is true. $\blacksquare$

A different solution: (it seems a bit long, but in reality it's pretty short to visualize; it seems longer since stuff is written formally not intuitively) Let $x = \max(x_1,\ldots,x_n), y = \max(y_1,\ldots,y_n)$. By scaling, WLOG assume $x = y = 1$. We will more strongly show $$ M + z_1 + z_2 + \cdots + z_{2n} \ge x_1 + \cdots + x_n + y_1 + \cdots + y_n $$Consider a bipartite graph $G$ with components $X = \{x_1,\ldots,x_n\}, Y = \{y_1,\ldots,y_n\}$. Place the vertices in that order only, as below: [asy][asy] dot("$x_1$",(1,0),dir(-90)); dot("$x_2$",(1.4,0),dir(-90)); label("$\cdots$",(1.6,0),dir(0)); dot("$x_n$",(2,0),dir(-90)); dot("$y_1$",(1,0.5),dir(90)); dot("$y_2$",(1.4,0.5),dir(90)); label("$\cdots$",(1.6,0.5),dir(0)); dot("$y_n$",(2,0.5),dir(90)); [/asy][/asy] Claim: We can draw $2n-1$ directed edges (segments) in $G$ such that: for any vertex $v \ne x$ there is a edge directed towards $v$. For any edge $e = \overrightarrow{e_1e_2}$, the value of $e_1$ is more than that of $e_2$. No two segments intersect in their interiors. Proof: We will draw the edges one by one. Start by drawing $x \to y$. Denote by $S$ the set of vertices which are endpoint of some drawn edge. So initially $S = \{x,y\}$. At any step, choose $v \in G \setminus S$ with max possible value. Note it suffices to draw a edge directed towards $v$ with other endpoint in $S$ and not intersecting any other edges. FTSOC such a edge cannot be drawn. For segments $s_1,s_2$, write $s_1 \sim s_2$ if $s_1,s_2$ intersect in their interiors, and $s_1 \not\sim s_2$ otherwise. Pick any $a_0$ in different component as of $v$ and consider $a_0v$. There must be some $a_1b_1 \in E(S)$ with $a_0v \sim a_1b_1$. Then we consider $va_1$. In general, if we consider $va_i$ then there is some $a_{i+1}b_{i+1} \in E(S)$ with $va_i \sim a_{i+1}b_{i+1}$. WLOG $a_1$ is to the right of $a_0$. By induction, it is not hard to see for any $i \ge 1$, we have $b_i$ is to the left of $v$ and $a_i$ is to the right of $a_0$ (we have to use no two $a_ib_i$ for $i \ge 1$ intersect). [asy][asy] size(200); dot("$v$",(1,0),dir(-90)); dot("$a_0$",(1,2),dir(90)); dot("$b_1$",(-4,0),dir(-90)); dot("$a_1$",(2,2),dir(90)); draw((1,0)--(1,2),red); draw((2,2)--(-4,0),green); dot("$a_2$",(3,2),dir(90)); dot("$b_2$",(-2.5,0),dir(-90)); draw((1,0)--(2,2),red); draw((3,2)--(-2.5,0),green); label("$\cdots$",(3.8,2)); label("$\cdots$",(-1.4,0)); dot("$b_i$",(-0.6,0),dir(-90)); dot("$a_i$",(4.6,2),dir(90)); draw((1,0)--(3,2),red); draw((-0.6,0)--(4.6,2),green); [/asy][/asy] But this would give us an infinite sequence $\{a_i\}$, contradiction $|S|$ is finite at any point. $\square$ Let $E$ be the edge set creates above. Note for any $x_iy_j \in E$, the values of $i + j$ are all distinct. Thus, \begin{align*} & M + z_1 + z_2 + \cdots + z_{2n} \ge 1 + \sum_{\overrightarrow{e_1e_2} \in E} \sqrt{\text{value} (e_1) \text{value} (e_2) } \ge 1 + \sum_{\overrightarrow{e_1e_2} \in E} \text{value} ( e_2) \\ & x_1 + \cdots + x_n + y_1 + \cdots + y_n = x + \sum_{\overrightarrow{e_1e_2} \in E} \text{value} (e_2) \end{align*}This completes the proof of the problem. $\blacksquare$

Another inequality! Since the equation is “homogenous”, we can scale max(x_1,…,x_n)=1 and max(y_1,…,y_n)=1, suppose they are x_a and y_b that =1. Because as z_1 increases, the inequality will only get stronger, so it suffices to show the minimum, which is z_k^2=x_iy_(k-i) s.t. the product of z_k^2 is the maximum of all possible products. Then we have M=1. Now, we can show that $M+z_1+…+z_{2n}\ge x_1+…+x_n+y_1+…+y_n$ by showing that for every value w, the LHS has at least as many values greater or equal to w than the RHS does. This is easy since if any arbitrary x_c and y_d are each greater than r ($0\le r\le 1$), then it also makes values z_(a+d) and z_(b+c) greater than r, since they are multiplied by 1. There there is a 1-1 correspondence, two values of z for every 1 value of each x and y. From here, we would have $(LHS/2n)^2\ge (RHS/2n)^2=(((x_1+…+x_n)/n+(y_1+…+y_n)/n)/2)^2\ge (sqrt{(x_1+…+x_n)/n(y_1+…+y_n)/n})^2=(x_1+…+x_n)/n(y_1+…+y_n)/n$, as desired. $\blacksquare$

We first notice that we can scale $\{x_i\}$ and $\{y_i\}$ such that $\max(x_i) = \max(y_i) = 1$. Using AM-GM, it suffices to prove \[M + z_2 + z_3 + \ldots + z_{2n} \ge (x_1 + \ldots + x_n) + (y_1 + \ldots + y_n).\] Claim: For each real $k$, there exists at least many terms on the LHS greater than $k$ as the RHS. Note this claim clearly finishes. Denote the sets $X = \{x_i: x_i>k\}$ and $Y = \{x_i: x_i>k\}$ with elements in increasing order. Consider the set of $|X|+|Y|-1$ elements \[\{X_1 Y_1, \cdots, X_1 Y_{|Y|}, X_2 Y_{|Y|}, \cdots, X_{|X|} Y_{|Y|}\}.\] As the index sums are all distinct, each product corresponds to a $z_i^2$ value which is at least as large. Along with $M$, this guarantees at least $|X|+|Y|$ terms on the LHS greater than $k$. $\blacksquare$