Exercice 14

On note $S(\sigma) = \sum_{k = 1}^{n} k\,\sigma(k)$.

1. La permutation $\sigma' = \sigma(i\ j)$ vérifie $\sigma'(i) = \sigma(j)$, $\sigma'(j) = \sigma(i)$, et coïncide avec $\sigma$ ailleurs. Seuls les termes d'indices $i$ et $j$ changent : $$S(\sigma') - S(\sigma) = i\sigma(j) + j\sigma(i) - i\sigma(i) - j\sigma(j) = (j - i)\big(\sigma(i) - \sigma(j)\big).$$

$$\boxed{S\big(\sigma(i\ j)\big) - S(\sigma) = (j - i)\big(\sigma(i) - \sigma(j)\big) > 0}$$ Échanger les images d'une inversion augmente donc strictement la somme. Le même calcul montre que, si $i < j$ et $\sigma(i) < \sigma(j)$, l'échange la diminue strictement.

2. L'ensemble $\mathcal{A}$ est fini, puisque $\mathfrak{S}_{n}$ l'est ; soit $\sigma$ telle que $S(\sigma) = \max\mathcal{A}$. Si $\sigma$ avait une inversion $(i, j)$, la question 1 fournirait $S\big(\sigma(i\ j)\big) > S(\sigma)$, ce qui est impossible. Donc $\sigma$ n'a aucune inversion : elle est croissante, et c'est l'identité. De même, si $S(\sigma) = \min\mathcal{A}$, aucun couple $i < j$ ne vérifie $\sigma(i) < \sigma(j)$, sinon l'échange diminuerait $S$ : $\sigma$ est strictement décroissante, et $\sigma(k) = n + 1 - k$ pour tout $k$. On calcule alors $$\sum_{k = 1}^{n} k^{2} = \frac{n(n + 1)(2n + 1)}{6}, \qquad \sum_{k = 1}^{n} k(n + 1 - k) = \frac{n(n + 1)^{2}}{2} - \frac{n(n + 1)(2n + 1)}{6} = \frac{n(n + 1)(n + 2)}{6}.$$

$$\boxed{\min\mathcal{A} = \frac{n(n + 1)(n + 2)}{6}, \text{ atteint pour } \sigma : k \mapsto n + 1 - k \text{ seulement}}$$ Pour $n = 3$, les six sommes valent $14$, $13$, $13$, $11$, $11$ et $10$ : on retrouve $\max = 14$ et $\min = 10$ ✓.

À retenir. C'est l'inégalité de réarrangement : pour deux suites de nombres, la somme des produits terme à terme est maximale quand on les range dans le même ordre, minimale quand on les range en ordre inverse. La preuve par échanges successifs est celle d'un algorithme de tri.