Международная олимпиада 2021, Санкт-Петербург, Россия, 2021 год

Докажите, что для любых вещественных чисел $x_1,$ $\ldots,$ $x_n$ выполняется неравенство $$\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|}$$

Комментарий/решение

Я это решил. Поверьте

bro got the whole chat laughing

Будем доказывать задачу индукцией по $n$, где база для $n=1$ очевидна. Заметим, что, если сдвинуть все переменные на число $d$, то попарные разности не поменяются, а справа появится $f(d) = \sum_{1 \leq i,j\leq n} \sqrt{|x_i+x_j+2d|}$. Важной частью этой задачи является понять как устроен график этой функции. Во первых, $f$ является суммой непрерывных функций, а значит сама непрерывна. Рассмотрим все точки $d$, в которых $x_i+x_j+2d = 0$ - $r_1, ..., r_t$, их конечное число и они делят числовую прямую на части $R_0, R_2, ..., R_t$. Заметим, что функция вида $\sqrt{|2x+c|}$ вогнута для всех $2x+c \neq 0$, тогда на каждом $R_i$ все функции будут вогнутыми, а значит $f$, как их сумма, тоже. Сделаем пометку, что из за непрерывности эти "куски" функций будут соприкасаться на концах интервалов. Так как функция стремится к бесконечности с обоих концов и функция вогнута на интервалах $R_0$ и $R_t$, то на этих интервалах она просто монотонно убывает и возрастает, соответственно. Рассмотрим минимальное из значений $f$ в точках $r_1, ..., r_t$ - $f(r_m)$. Допустим, что у функции есть значение $f(x)\leq f(r_m)$ и оно не совпадает с концом какого то интервала, тогда пусть этот $x$ лежит на интервале $R_j$ (очевидно, что $j \neq 0,t$, так как функция монотонна на них и больше, чем конец интервала), и так как функция на нем вогнута, то $f(x) \geq min(f(r_j), f(r_{j+1})) \geq f(r_m))$, причем равенство только если $x$ совпадает с каким то из концов интервала. Мы только что доказали, что $f(x) \geq f(r_m)$ для всех $x$, тогда достаточно доказать наше неравенство в случае, когда $d=r_m$, тогда у нас будет новое неравенство $\sum_{i=1}^n \sum_{j=1}^n \sqrt{|y_i-y_j|}\leqslant \sum_{i=1}^n \sum_{j=1}^n \sqrt{|y_i+y_j|}$, где каждое $y_i=x_i+d$, тогда $y_i+y_j=0$ для каких то $1 \leq i,j\leq n$, тогда $\sqrt{|y_i+y_k|} = \sqrt{|y_j-y_k|}$, тогда эти члены сократятся и останется неравенство для $n-2$ переменных (или $n-1$, если $i$ был равен $j$)

Покажите, что неравенство }^n \sqrt{|x_i+x_j|} \] выполняется для всех действительных чисел $x_1,\ldots x_n.$

Пусть $f(x)=\sum_{i=1}^n \sum_{j=1}^n \sqrt{|(x_i+x)+(x_j+x)|}$.

Имеем $\lim_{x_\to\infty}=\lim_{x_\to-\infty}=\infty$ и $f$ непрерывен. Таким образом, существует $x$, для которого $f(x)$ является минимальным. Поскольку $\sqrt{x}$ выпукла, $f(x)$ минимальна при $2x=x_i+x_j$.

При $i=j$ мы можем свести неравенство к $n-1$ переменным.

Для $i\neq j$ мы можем свести неравенство к $n-2$ переменным.