Théorie > Inégalités > Inégalités portant sur l'ordre

Inégalité de réarrangement

Supposons être en présence de deux suites de nombres, comme par exemple $(1,2,3)$ et $(4,5,6)$. L'inégalité de réarrangement nous indique comment on peut coupler ces nombres deux par deux de sorte que la somme des produits soit la plus grande possible. Intuitivement pour notre exemple, la plus grande somme que l'on peut obtenir est $1\cdot4 + 2\cdot 5 + 3 \cdot 6 = 32$, et il suffit de tester les $6$ différentes possibilités pour s'apercevoir qu'il s'agit effectivement de la meilleure option.

L'inégalité de réarrangement dit que notre intuition est toujours la bonne. Elle mentionne également que pour obtenir la plus petite somme, il faut coupler les nombres en sens inverse (sur notre exemple, $1\cdot 6 + 2 \cdot 5 + 3 \cdot 4 = 28$).

Inégalité de réarrangement
Soient $x_1 \leq \ldots \leq x_n$ et $y_1 \leq \ldots \leq y_n$ des nombres réels. Pour toute permutation $\sigma$ de $\{1, \ldots, n\}$, on a
$$x_1 y_n + \ldots + x_n y_1 \leq x_1 y_{\sigma(1)} + \ldots + x_n y_{\sigma(n)}\leq x_1 y_1 + \ldots + x_n y_n.$$

La notation avec $\sigma$ ne doit pas perturber le lecteur : elle permet simplement de dire que l'on permute les $y_i$.

Démonstration
Pour démontrer que la plus grande somme est atteinte lorsque les suites sont dans le même ordre, on prouve que dans tous les autres cas la somme n'est pas maximale. Partons donc d'une somme où les suites ne sont pas dans le même ordre et montrons qu'on peut l'augmenter en changeant l'ordre. Considérons
$$x_1 y_1 + \ldots + x_n y_n$$ avec $x_1, \ldots, x_n$ et $y_1, \ldots, y_n$ qui ne sont pas dans le même ordre, c'est-à-dire avec $x_i < x_j$ mais $y_i > y_j$ pour certains $i, j$. On peut alors directement augmenter cette somme en inversant $y_i$ et $y_j$. En effet, on a
$$x_i y_i + x_j y_j \leq x_i y_j + x_j y_i$$ puisque cela peut se factoriser en
$$(x_i - x_j)(y_i-y_j) \leq 0$$ qui est toujours vrai comme $x_i < x_j$ et $y_i > y_j$. On vient donc de montrer que dans n'importe quel cas où les deux suites ne sont pas dans le même ordre, la somme n'est pas maximale. Cela prouve que le maximum est atteint lorsque les suites sont dans le même ordre.

De la même façon, on montre que le minimum est atteint lorsque les suites sont dans des ordres opposés.