IMO 2021 is finally over. As usual I skimmed through the question and focus on the inequality problem where I usually perform the best. It was Q2 this year, but it is not an average Q2.
It turned out to be as hard as Q3 (mean score 0.375 against Q3's 0.372, but Q2 gives out more partial scores and more zeros), both harder than this year's Q6 (mean 0.481). Possibly one of the most controversial Q2 in IMO history. What makes it so interesting? Here are my thoughts.
First let us look at the question.
Problem (IMO2021 Q2). Show that
$\sum _{i,j} \sqrt{|x_i-x_j|} \leq \sum _{i,j} \sqrt{|x_i+x_j|}$
for all real numbers $x_1,...,x_n$.
If you have already spent time onto this problem, here is the solution. This is similar to the solution mentioned by TheUltimate123 in the AoPS thread.
Claim 1. The case $n = 0,1$ is trivial.
Claim 2. LHS is invariant upon shifting all $x_i$ by a constant (let us simply call that "shifting" for the rest of the solution)
Claim 3. If $x_k = 0$ for some $k$ then the $x_i$-related terms on both sides are the same which is
$2\sum _{i\neq k} \sqrt{|x_i|}$. Therefore we now WLOG assume that all terms are non-zero.
Claim 4. If $x_k+x_l=0$ for some $k\neq l$ then the $x_k$ or $x_l$-related terms on both sides are also the same, which is $2\sqrt{2|x_k|} + \sum _{i\neq k,l}(\sqrt{|x_i-x_k|}+\sqrt{|x_i+x_k|})$.
Claim 5. RHS is not minimal upon shifting unless $x_k+x_l=0$ for some $k,l$.
Proof: Jensen gives that
$\sqrt{|x+y+\varepsilon|} + \sqrt{|x+y-\varepsilon|} \leq 2\sqrt{|x+y|}$
for $x+y\neq 0$ and $\varepsilon \leq |x+y|$.
Summing over all $x_i$ gives
$\sum _{i,j} (\sqrt{|x_i+x_j+\varepsilon|} + \sqrt{|x_i+x_j-\varepsilon|}) \leq 2\sqrt{|x_i+x_j|}$.
for sufficiently small $\varepsilon$. Therefore a shift of either $\varepsilon /2$ or $-\varepsilon /2$ would give a smaller RHS while having LHS fixed.
Note that $x_k+x_l\neq 0$ is required to maintain convexity of $\sqrt{|x+y|}$.
Therefore the induction is completed. If $x_k=0$ for some $k$ then we reduce to the $n-1$ case by claim 3. Otherwise shift until $x_k+x_l=0$ for some $k,l$, then reduce to the $n-2$ case by claim 4.
The above also gives the equality case in full. Firstly adding arbitrarily many zero terms does not affect the sum. If we assume non-zero terms then the only instance where RHS decreases is by shifting, so in order to obtain equality the terms must be canceled pair by pair without the need of shifting. We therefore conclude that equality holds if and only if the terms are symmetric along zero.
*
There are alternative solutions using completely different approaches like the use of integral to prove the more generalized case $E|X+Y|^{1/2} \geq E|X-Y|^{1/2}$ for random variables $X,Y$. Even more fascinating, one used the integral
$\sqrt{|a+b|}-\sqrt{|a-b|} = \frac{1}{\sqrt{2\pi}}\int ^{\infty}_0 x^{-3/2}(\cos (a-b)x-\cos (a+b)x)dx$
$= \frac{1}{\sqrt{2\pi}}\int ^{\infty}_0 2 x^{-3/2} \sin ax \sin bx dx$.
It is also note worthy that the original problem uses the exponent $\alpha = 1/2$. The statement holds for all $\alpha \in (0,2]$. Convexity works all the way up to $\alpha = 1$ but college techniques is absolutely necessary for higher $\alpha$. One approach is to use linear algebra and binomial theorem for non-integer exponents(notice that when $\alpha = 2$ it simply reduces to prove that $4\sum x_i x_j \geq 0$ which is obvious. But then for $\alpha \in (1,2)$ you can also write $|x_i-x_j|^{\alpha} = (x_i^2+x_j^2-2x_ix_j)^{\alpha /2}$, then you may expand and compare both sides using positive-definiteness), and the other is a generalization of that integral identity (with the help of gamma function).
You might have noticed something here already: the abundance of calculus solutions, the clear generalization to something famous and common in undergraduate maths, and the flexibility in exponential (cf. most $a,b,c$ type inequalities that you saw in 2000s-2010s IMOs), all suggests that this is a very good question for undergraduate contests.
However if we consider IMO to be the pool of the most talented math students in the world (even better than those participating undergraduate contests on average), why is this a hard problem to them? And why did they perform poorly at the end?
I figured out the solution almost immediately, like within 15 minutes, and the flow of thoughts is as follows: the shift is clear immediately. Then I tried to solve the case $n=2$, which is not easy already. By using the parametrization $x_2 = rx_1$, it is found that the equality is tight if $r=-1$. Putting back to the inequality with $x_1$ and $x_2$, it can be found that when $x_1=-x_2$ the terms on both sides are equal. The cancellation trick is soon found to be working with larger $n$. We now know that induction may work as long as we can reduce to these cases. (I missed the case $x_k=0$ when I first solved the question, so I didn't get a 7 in that sense...)
By reducing to these case, we must show that shifting to these case gives a smaller RHS, and this is what we need to prove. We applied Jensen and showed that we can always get smaller as long as $x_k+x_l \neq 0$ so we are done.
...or not?
You might have spotted the problem already. The hard bit of the question is the indirect relation between the fact that you can shift to reduce RHS and the goal that you can shift to a smaller RHS that $x_k+x_l=0$.
It goes through only if you have a calculus sense, or else it could trap you forever.
For starter let us consider to shift by the maximum possible distance $\pm\min |x_i+x_j|/2 = \pm t$ so that we reached a singular point (where $x_k+x_l=0$...). The problem is: we only know that a either a shift of $+t$ or $-t$ gives a smaller RHS but not necessarily both. If you shift to the point where $x_k+x_l=0$ you are not guaranteed a smaller RHS.
Or, if you shift little by little to reduce RHS, can you guarantee that you end up with a singular point?
These are never a problem if you know calculus argument, and they can only be understood via calculus argument.
From a global point of view, the sum is definitely increasing with large enough shifts. Since the sum is also bounded below and is continuous, there must be a global minimum. Since the minimum does not occur at the smooth part it must be at one of the singular point. We can shift directly to that point to complete the induction.
To shift gradually you may argue that the derivative between two singular points do not change signs so one of the two neighboring singular point must be a local minimum [or even weaker, a local minimum with respect to the closed interval bounded by the two singular points]. Alternatively, since we know that $(\sqrt{x})' = 1/(2\sqrt{x})$ which rockets as $x\to 0$, we argue that the derivative of $\sqrt{|x_k+x_l|}$ overwhelms all other terms as we shift $x_k+x_l\to 0$, so that must incur a minimum [hence even singular point is a local minimum].
And how can you argue that by "elementary means"? Probably not, unless the official solution suggests something spectacular.
If you check everything else in the solution they are pretty standard. induction of course, simple special case ($x_k=0$) and a more complicated special case ($x_k+x_l=0$), substitution [in fact, instead of a shift, we may apply the substitution $x_i = y_i+t$ to achieve the same] to hold one side invariant, Jensen on convex functions --- these are all standard tricks in IMO. It is the final link that completes the solution, is hard to realize and that link is, regrettably unavoidable.
It is a beautiful and insightful inequality. Again quoting someone in the thread -- the beauty of this problem is that $n=2$ provides everything you need: minimal condition and the shifting. (Although to be fair, $n=2$ hides the technical problem as described above, and you will only meet that at $n\geq 3$.) It simply requires Jensen (or even just elementary comparison because it is just square root) in a two line calculation. We do not need 30 lines of machinery like other IMO inequalities did.
We can continue the list and praise the problem in many more different ways. The only criticism is that the problem unfortunately does not belong to IMO.
*
I last wrote about IMO problems in 2006, before this blog opened. I wrote that in my previous blog, a site that is long abolished (at least I do not have to worry about Blogger closing soon...yet).
I was of course, too immature to understand what happened -- I copied someone else's solution and put it on my blog. For whatever reason that post received tons of comments out of nowhere: recalling that discussion now I believe that those people are truly qualified to do these IMO problems. It is still a mystery up to now how did they found my post (out of a blog that never talked about advanced mathematics otherwise) and open a contextful discussion there, but this is the beauty of Internet in the 2000s.
Without running into a nostalgic loop, let me finish with that particular IMO problem that I discussed back in 2006. That problem was 2001 Q2 -- another Q2, another inequality, and another problem that allows elegant solution using Jensen's inequality.
Problem (IMO2001 Q2). Prove that for all positive real $a,b,c$ the inequality $\sum _{cyc} \frac{a}{\sqrt{a^2+8bc}} \geq 1$ holds.
No comments:
Post a Comment