IMO 2021 · Problem 2

Show that the inequality \[ \sum_{i=1}^{n}\sum_{j=1}^{n}\sqrt{|x_i-x_j|} \leqslant \sum_{i=1}^{n}\sum_{j=1}^{n}\sqrt{|x_i+x_j|} \] holds for all real numbers \(x_1,\ldots,x_n\).

Official text of the problem. Official problem paper (PDF)

Solution

We first prove an elementary lemma.

Lemma. If \(t_1,\ldots,t_m\) and \(c_1,\ldots,c_m\) are real numbers with \(\sum_{i=1}^{m}c_i=0\), then \[ \sum_{i=1}^{m}\sum_{j=1}^{m}c_ic_j\sqrt{|t_i-t_j|}\leq 0. \]

Proof. Reorder the pairs \((t_i,c_i)\) so that \[ t_1\leq t_2\leq\cdots\leq t_m. \] Repeated values are allowed. The case \(m=1\) is immediate, so assume \(m\geq2\).

Put \[ a_{ij}=\sqrt{|t_i-t_j|}, \qquad s_0=0,\qquad s_i=\sum_{k=1}^{i}c_k. \] Thus \(s_m=0\) and \(c_i=s_i-s_{i-1}\). For \(1\leq i,j\leq m-1\), define \[ b_{ij}=a_{ij}-a_{i+1,j}-a_{i,j+1}+a_{i+1,j+1}. \] Expanding and using \(s_0=s_m=0\) gives \[ \sum_{i,j=1}^{m}c_ic_ja_{ij} = \sum_{i,j=1}^{m-1}b_{ij}s_is_j. \tag{1} \]

We will show that the quadratic expression on the right is nonpositive.

First, \(b_{ij}=b_{ji}\), and \(b_{ij}\geq0\) whenever \(i\ne j\). Indeed, for \(i<j\), set \[ h=t_{i+1}-t_i,\qquad u=t_j-t_{i+1},\qquad v=t_{j+1}-t_j, \] all of which are nonnegative. Then \[ b_{ij} = \bigl(\sqrt{u+h}-\sqrt u\bigr) - \bigl(\sqrt{u+v+h}-\sqrt{u+v}\bigr) \geq0. \] Here we used that, for fixed \(h\geq0\), the function \(\sqrt{u+h}-\sqrt u\) is nonincreasing for \(u\geq0\). For \(h=0\) this is immediate; for \(h>0\), it follows from \[ \sqrt{u+h}-\sqrt u =\frac{h}{\sqrt{u+h}+\sqrt u}. \]

Second, every row sum of \((b_{ij})\) is nonpositive. Telescoping gives \[ \begin{aligned} r_i:=\sum_{j=1}^{m-1}b_{ij} &=a_{i1}-a_{i+1,1}-a_{im}+a_{i+1,m}\\ &=\sqrt{t_i-t_1}-\sqrt{t_{i+1}-t_1} -\sqrt{t_m-t_i}+\sqrt{t_m-t_{i+1}} \leq0. \end{aligned} \] Both differences in the last line are nonpositive.

Consequently, \[ \sum_{i,j=1}^{m-1}b_{ij}s_is_j = \sum_{i=1}^{m-1}r_i s_i^2 - \sum_{1\leq i<j\leq m-1}b_{ij}(s_i-s_j)^2 \leq0. \] Together with (1), this proves the lemma. \(\square\)

Now apply the lemma to the \(2n\) numbers and coefficients \[ (t_1,\ldots,t_{2n}) =(x_1,\ldots,x_n,-x_1,\ldots,-x_n), \] \[ (c_1,\ldots,c_{2n}) =(\underbrace{1,\ldots,1}_{n}, \underbrace{-1,\ldots,-1}_{n}). \] The coefficients sum to zero. The two groups of terms whose coefficients have the same sign each contribute \(\sum_{i,j=1}^{n}\sqrt{|x_i-x_j|}\), while the two groups with opposite signs each contribute \(-\sum_{i,j=1}^{n}\sqrt{|x_i+x_j|}\). Hence the lemma yields \[ 2\sum_{i,j=1}^{n}\sqrt{|x_i-x_j|} - 2\sum_{i,j=1}^{n}\sqrt{|x_i+x_j|} \leq0, \] which is the required inequality. The lemma allows repeated and zero values, so these cases are included.

The solution was checked against the official IMO shortlist solutions.