Shortlist 2021, A4¶

Domaine : Algèbre · Difficulté : ★★☆☆☆ · Proposé par : non indiqué

Concepts : Convexité, inégalité de Jensen, lissage

Solution officielle : Shortlist officielle 2021 (avec solutions), p. 18 (page 18 du PDF)

Problème 2 de l'OIM 2021

Ce problème a été choisi parmi ceux de la shortlist pour l'épreuve de l'OIM 2021, où il était le problème 2 (jour 1).

Énoncé¶

Show that for all real numbers \(x_1, \ldots, x_n\) the following inequality holds:

\[\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|}.\]

Indices : les idées clés

Translater toutes les variables (solution 1) : le membre de gauche ne change pas, le membre de droite devient une fonction \(H(t)\) de la translation \(t\).
Concavité (solution 1) : \(H\) est concave par morceaux, donc son minimum sur un segment est atteint en une extrémité ; on se ramène au cas où \(x_i + x_j = 0\) pour deux indices.
Réduction de \(n\) (solution 1) : si \(x_i = 0\) ou \(x_i + x_j = 0\), on retire ces variables, ce qui diminue les deux membres de la même quantité.
Représentation intégrale (solution 2) : \(\sqrt{|p|}\) est proportionnel à \(\int_0^\infty \frac{1 - \cos(px)}{x\sqrt{x}}\,dx\), ce qui écrit la différence des deux membres comme l'intégrale d'un carré.

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2021 (deux solutions et deux remarques).

Solution 1¶

Si l'on ajoute \(t\) à toutes les variables, le membre de gauche ne change pas et le membre de droite devient

\[H(t) := \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{|x_i + x_j + 2t|}.\]

Soit \(L\) la valeur du membre de gauche, et \(T\) assez grand pour que \(H(-T)\) et \(H(T)\) soient tous deux supérieurs à \(L\). Les points (non nécessairement distincts) \(p_{i,j} := -(x_i + x_j)/2\), avec \(T\) et \(-T\), découpent la droite réelle en segments et en deux demi-droites ; sur chacun de ces segments et demi-droites, la fonction \(H\) est concave, car \(f(t) := \sqrt{|\ell + 2t|}\) est concave sur chacun des intervalles \((-\infty, -\ell/2]\) et \([-\ell/2, +\infty)\).

Soit \([a, b]\) le segment contenant \(0\). La concavité entraîne \(H(0) \geq \min\{H(a), H(b)\}\) et, comme \(H(\pm T) > L\), il suffit de prouver les inégalités \(H(-(x_i + x_j)/2) \geq L\), c'est-à-dire de démontrer l'inégalité initiale lorsque toutes les variables ont été translatées de sorte que deux d'entre elles, \(x_i\) et \(x_j\), aient une somme nulle. Dans la suite, on note encore \(x_i\) les variables translatées.

Si \(i = j\), c'est-à-dire si \(x_i = 0\) pour un indice \(i\), on peut retirer \(x_i\), ce qui diminue les deux membres de \(2\sum_{k \neq i} \sqrt{|x_k|}\). De même, si \(x_i + x_j = 0\) pour des indices distincts \(i\) et \(j\), on peut retirer \(x_i\) et \(x_j\), ce qui diminue les deux membres de

\[2\sqrt{2|x_i|} + 2 \sum_{k \neq i, j} \left(\sqrt{|x_k + x_i|} + \sqrt{|x_k + x_j|}\right).\]

Dans les deux cas, on s'est ramené à une inégalité avec moins de variables. Il reste à remarquer que pour \(n = 0\) et \(n = 1\) l'inégalité est triviale. \(\blacksquare\)

Solution 2¶

Pour \(p\) réel, considérons l'intégrale

\[I(p) = \int_0^\infty \frac{1 - \cos(px)}{x\sqrt{x}}\,dx,\]

qui converge clairement vers un nombre strictement positif (pour \(p \neq 0\)). Par le changement de variable \(y = |p|x\), on voit que \(I(p) = \sqrt{|p|}\, I(1)\). Avec la formule trigonométrique \(\cos(\alpha - \beta) - \cos(\alpha + \beta) = 2\sin\alpha \sin\beta\), on obtient

\[\sqrt{|a + b|} - \sqrt{|a - b|} = \frac{1}{I(1)} \int_0^\infty \frac{\cos((a - b)x) - \cos((a + b)x)}{x\sqrt{x}}\,dx = \frac{1}{I(1)} \int_0^\infty \frac{2\sin(ax)\sin(bx)}{x\sqrt{x}}\,dx,\]

d'où l'inégalité découle immédiatement :

\[\sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{|x_i + x_j|} - \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{|x_i - x_j|} = \frac{2}{I(1)} \int_0^\infty \frac{\left(\sum_{i=1}^{n} \sin(x_i x)\right)^2}{x\sqrt{x}}\,dx \geq 0. \qquad \blacksquare\]

Remarques¶

Remarque 1 (généralisation). L'inégalité plus générale

\[\sum_{i=1}^{n} \sum_{j=1}^{n} |x_i - x_j|^r \leq \sum_{i=1}^{n} \sum_{j=1}^{n} |x_i + x_j|^r\]

est vraie pour tout \(r \in [0, 2]\). La solution 1 se recopie mot pour mot pour tout \(r \in [0, 1]\), mais pas pour \(r > 1\). Dans la solution 2, en mettant \(x^{1+r}\) au dénominateur à la place de \(x\sqrt{x}\), on démontre l'inégalité pour tout \(r \in (0, 2)\) ; les cas \(r = 0\) et \(r = 2\) se vérifient facilement à la main.

Remarque 2. L'intégrale de la solution 2 se calcule explicitement : \(I(1) = \sqrt{2\pi}\).