↵ pour ouvrir · ↑↓ pour naviguer · Esc pour fermer
Sur une ligne de cases, on place des jetons numérotés 1 à 2n dans un ordre quelconque. On effectue des opérations : choisir deux jetons adjacents et les échanger.
On définit le nombre d'inversions comme le nombre de paires (i, j) avec i < j mais le jeton i est à droite du jeton j.
1. Échanger deux éléments adjacents ai et ai₊₁ : si ai < ai₊₁, c'était "en ordre" → après échange, c'est une inversion (+1). Si ai > ai₊₁, c'était une inversion → après, en ordre (−1). Les paires non adjacentes ne sont pas affectées. Donc l'inversion varie de ±1. ✓
2. Le nombre d'inversions final (suite triée) = 0. Chaque échange change la parité du nombre d'inversions. Donc le nombre d'échanges minimum a la même parité que le nombre d'inversions initial.
3. (2,1,4,3) : inversions = {(2,1), (4,3)} = 2 inversions. Pour trier → nombre minimum d'échanges de même parité que 2, soit pair. 3 est impair → impossible en exactement 3 échanges (minimum = 2).