62nd International Mathematical Olympiad / IMO 2021 / | Problem 2 - Solution - 21 July 2021

Problem 2. Show that the inequality

$\sum_{i = 1}^{n} \sum_{j = 1}^{n} \sqrt{| x_{i} - x_{j} |} \leq \sum_{i = 1}^{n} \sum_{j = 1}^{n} \sqrt{| x_{i} + x_{j} |}$

holds for all real numbers x₁, . . . , x_n.

proposed by Calvin Deng, Canada

Solution

If $x_i = 0$ for some $i$ , WLOG $x_n = 0$ . Then by induction on $(x_1, x_2, \dots, x_{n - 1})$ ,

$\begin{align*} \sum_{1 \le i,j \le n} \sqrt{|x_i + x_j|} &= 2 \cdot \sum_{1 \le i \le n - 1} \sqrt{|x_i|} + \sum_{1 \le i ,j \le n - 1} \sqrt{|x_i + x_{j}|} \\ &\ge 2 \cdot \sum_{1 \le i \le n - 1} \sqrt{|x_i|} + \sum_{1 \le i ,j \le n- 1} \sqrt{|x_i - x_j|} \\ &= \sum_{1 \le i,j \le n} \sqrt{|x_i - x_j|} \end{align*}$
Otherwise, we could assume that $x_i \not= 0$ for all $i$ , and therefore, $\sqrt{|x_i + x_j|} + \sqrt{|x_i - x_j|} > 0$ for all $i,j$ , then WLOG $|x_1| \le |x_2| \le |x_3| \le \dots \le |x_n|$ , and define $y_i = |x_{i}| - |x_{i - 1}|$ , where $x_0 = 0$ . Also, write $x_i = \varepsilon_i |x_i|$ for all $i$ .
$\begin{align*} \sum_i \sum_j \sqrt{|x_i + x_j|} - \sqrt{|x_i - x_j|} &= \sum_i \sum_j \frac{|x_i + x_j| - |x_i - x_j|}{\sqrt{|x_i + x_j|} + \sqrt{x_i - x_j|}} \\ &= 2 \sum_i \sum_j \frac{\varepsilon_i \varepsilon_j \min(|x_i|,|x_j|)}{\sqrt{|x_i + x_j|} + \sqrt{|x_i - x_j|} } \\ &\ge \frac{2}{\max_{i,j} \sqrt{|x_i + x_j|} + \sqrt{|x_i - x_j|}} \left( \sum_i \sum_j \varepsilon_i \varepsilon_j \min(|x_i|,|x_j|) \right) \\ &\ge \frac{2}{\max_{i,j} \sqrt{|x_i + x_j|} + \sqrt{|x_i - x_j|}} \left( \sum_i \sum_j \varepsilon_i \varepsilon_j \sum_{k \le \min(i,j)} y_k \right) \\ &= \frac{2}{\max_{i,j} \sqrt{|x_i + x_j|} + \sqrt{|x_i - x_j|}} \left( \sum_k y_k \sum_{i,j \ge k} \varepsilon_i \varepsilon_j \right) \\ &= \frac{2}{\max_{i,j} \sqrt{|x_i + x_j|} + \sqrt{|x_i - x_j|}} \left( \sum_k y_k \left( \sum_{i \ge k} \varepsilon_i \right)^2 \right) \\ &\ge 0 \end{align*}$