# Proving $\sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i-x_j|}\le \sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i+x_j|}$.

IMO 2021, Problem 2.

Let $$n$$ be an integer $$\ge 2$$ and $$x_1,x_2,...,x_n$$ be $$n$$ reals. prove that

$$\sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i-x_j|}\le \sum_{i=1}^n\sum_{j=1}^n\sqrt{|x_i+x_j|}$$

I wrote the left sum as $$2\sum_{i=2}^n\sum_{j=1}^{i-1}\sqrt{|x_i-x_j|}$$ and the right one as $$2\sum_{i=2}^n\sum_{j=1}^{i-1}\sqrt{|x_i+x_j|}+\sum_{i=1}^n\sqrt{2|x_i|}$$

but, it seems this is not a good starting point.

• Thanks a lot for editing the Title. Jul 25, 2021 at 22:48
• You're welcome, @hamam_Abdallah. Jul 25, 2021 at 22:49
• This question is very related, although the answer there might use more advanced techniques that what is expected to solve this problem. Also, is this 2021 IMO Problem 2? If so, that should be mentioned in this question. Jul 25, 2021 at 22:53
• There’s bound to be an AOPS solution. This is Problem 2 of this year’s IMO. Jul 25, 2021 at 22:54
• If you’re interested in an elementary answer, you should be able to find sketches there: artofproblemsolving.com/community/c6h2625850p22697952 . But again – this is an IMO P2. This isn’t supposed to be easy to find. The Italian team was ranked 7th – and none of them got the solution in 4h30. Only one of the Chinese contestants did – and that team was ranked first! Jul 25, 2021 at 23:20

This is certainly not an answer expected in IMO, but the proof works for far more general cases, see this posting, for instance.

Note that

$$\frac{1}{c} \int_{0}^{\infty} \frac{1-\cos (as)}{s^{3/2}} \, \mathrm{d}s = |a|^{1/2} \quad \text{for any} \quad a \in \mathbb{R},$$

where $$c = \int_{0}^{\infty} \frac{1-\cos t}{t^{3/2}} \, \mathrm{d}t \in (0, \infty)$$. This is easily proved by substituting $$t = |a|s$$. Then

\begin{align*} &\sum_{i,j} |x_i + x_j|^{1/2} - \sum_{i,j} |x_i - x_j|^{1/2} \\ &= \frac{1}{c} \int_{0}^{\infty} \frac{1}{s^{3/2}}\biggl( \sum_{i,j} \cos((x_i- x_j)s) - \cos((x_i + x_j)s) \biggr) \, \mathrm{d}s \\ &= \frac{1}{c} \int_{0}^{\infty} \frac{1}{s^{3/2}}\biggl( \sum_{i,j} 2\sin(x_i s)\sin(x_j s) \biggr) \, \mathrm{d}s \\ &= \frac{1}{c} \int_{0}^{\infty} \frac{2}{s^{3/2}}\biggl( \sum_{i} \sin(x_i s) \biggr)^2 \, \mathrm{d}s \\ &\geq 0. \end{align*}

Of course, it would be fun to have a more elementary solution.

• That's... very neat. Jul 25, 2021 at 23:28
• I was looking for this solution for few days already, thank you! Jul 26, 2021 at 10:15