Le photographe de classe

Supposons un appariement optimal $\sigma$ contenant un croisement : il existe deux indices $a<b$ tels que $t_a\le t_b$ mais $h_{\sigma (a)}\ge h_{\sigma (b)}$. Décroisons cet appariement en associant $t_a\to h_{\sigma (b)}$ et $t_b\to h_{\sigma (a)}$. Posons $u=t_a$, $v=t_b$, $x=h_{\sigma (b)}$ et $y=h_{\sigma (a)}$ de sorte que $u\le v$ et $x\le y$. Il s'agit de prouver que l'écart maximal après décroisement n'est pas supérieur à celui d'avant : $$\max (|u-x|,|v-y|)\le \max (|u-y|,|v-x|)$$ En analysant les positions relatives sur la droite réelle, on établit que $|u-x|\le \max (|u-y|,|v-x|)$ et $|v-y|\le \max (|u-y|,|v-x|)$. Le maximum des écarts n'est donc pas dégradé par cette opération. En itérant ce processus de décroisement (le nombre d'inversions de l'appariement constituant un variant de boucle strictement décroissant), on converge vers l'appariement trié du glouton qui est donc optimal.