Un exercice plutôt original mais néanmoins classique ! Dans cet article nous allons démontrer l’inégalité du réordonnement, c’est un exercice autour des permutations qui a une démonstration élémentaire.
Enoncé
Commençons la correction de cet exercice !
Corrigé
Nous allons d’abord démontrer la seconde inégalité, la première en découlera naturellement. Pour cela, nous allons faire un raisonnement par récurrence.
Initialisation : On suppose que n = 2. Dans ce cas, on veut montrer :
a_1 b_{\sigma(1)} +a_2 b_{\sigma(2)} \leq a_1 b_{1} +a_2 b_2 Or, on a :
\begin{array}{ll}
& a_1 b_{1} +a_2 b_2 - a_1 b_{\sigma(1)} +a_2 b_{\sigma(2)} \\
= & a_1 (b_1 - b_{\sigma(1)}) + a_2 (b_2- b_{\sigma(2)})\\
\geq & 0 + 0 = 0
\end{array}Ainsi :
a_1 b_{\sigma(1)} +a_2 b_{\sigma(2)} \leq a_1 b_{1} +a_2 b_2 Hérédité :
Soit n \in \N, n \geq 2 fixé. On suppose que
\forall \sigma \in S_n , \sum_{i=1}^n a_i b_{\sigma(i)} \leq \sum_{i=1}^n a_i b_iSoit \sigma \in S_{n+1} . Soit i tel que \sigma (i) = n +1 . On pose aussi j = \sigma(n+1). On considère alors :
a_i b_{\sigma(i)} + a_{n+1} b_{\sigma(n+1)}Or,
\begin{array}{ll}
&a_ib_j+a_{n+1}b_{n+1}-(a_i b_{\sigma(i)} + a_{n+1} b_{\sigma(n+1)})\\
=&a_ib_j+a_{n+1}b_{n+1}-(a_i b_{n+1} + a_{n+1} b_{j})\\
=&a_i(b_j-b_{n+1})+a_{n+1}(b_{n+1}-b_j)\\
=&(a_{n+1}-a_i)(b_{n+1}-b_j) \geq 0
\end{array}On a donc :
\begin{array}{ll}
& (a_{n+1}-a_i)(b_{n+1}-b_j) \geq 0 \\
\iff & a_ib_j+a_{n+1}b_{n+1}\geq (a_i b_{\sigma(i)} + a_{n+1} b_{\sigma(n+1)})
\end{array}Posons alors la permutation \sigma' \in S_n
\sigma'(k) = \left\{ \begin{array}{ll}
j & \text{si } k = i \\
\sigma(k) & \text{sinon}
\end{array}\right.Par l’inégalité au-dessus, on a alors :
\sum_{i=1}^{n+1} a_i b_{\sigma'(i)} \leq \sum_{i=1}^n a_i b_{\sigma(i)} +a_{n+1}b_{n+1}Or, par hypothèse de récurrence, on a :
\sum_{i=1}^n a_i b_{\sigma(i)} \leq \sum_{i=1}^n a_i b_iAinsi, en combinant ces deux inégalités :
\sum_{i=1}^{n+1} a_i b_{\sigma'(i)} \leq \sum_{i=1}^{n} a_i b_{i}+a_{n+1}b_{n+1} \leq \sum_{i=1}^{n+1} a_i b_{i} Ainsi, l’hérédité est vérifiée. On a donc démontré la seconde inégalité, pour montrer la première, on remarque que :
\begin{array}{ll}
&\displaystyle \sum_{i=1}^n a_i b_{n+1-i} \leq \sum_{i=1}^n a_i b_{\sigma(i)} \\
\iff &\displaystyle \sum_{i=1}^n a_i (-b_{\sigma(i)} ) \leq \sum_{i=1}^n a_i (-b_{n+1-i}) \end{array}En posant alors c_i = -b_{n+1-i}, on se ramène alors à la seconde inégalité. La première inégalité est donc aussi vraie !
Ainsi, on a bien démontré l’inégalité du réordonnement.
