Invariants

Un invariant est une propriété qu'aucun mouvement autorisé ne modifie. Faites glisser les pièces du taquin, découpez les cases de l'échiquier ou ajoutez des ponts à Königsberg, et la page gardera l'invariant bien en vue : la parité du nombre d'inversions, les cases noires face aux blanches, les masses terrestres avec un nombre impair de ponts. Lorsque cette valeur diffère entre le point de départ et l'objectif, aucune suite de mouvements ne permet de l'atteindre.

Exemple résolu — Invariants

Inversions	1
L'invariant : inversions mod 2	impair
Coups depuis la solution	inatteignable

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Invariants

Un invariant est une quantité qu'aucun mouvement autorisé ne modifie. Si sa valeur de départ diffère de celle de l'objectif, ce dernier ne pourra jamais être atteint quels que soient les mouvements tentés. Et nul besoin d'effectuer une recherche pour le savoir.

Ce que signifie chaque symbole

I: l'invariant : ici la parité du nombre d'inversions, la différence entre les cases noires et blanches, ou le nombre de masses terrestres ayant un nombre impair de ponts
d(v): le degré d'une masse terrestre v : le nombre de ponts qui y aboutissent

D’où vient la formule

Pourquoi un glissement conserve la parité. Lisez les huit pièces ligne par ligne, en ignorant le trou. Un glissement latéral ne modifie aucunement cet ordre de lecture. Un glissement vertical déplace une pièce de trois positions dans cette lecture, la faisant passer par-dessus les deux pièces situées entre son ancienne et sa nouvelle case. Chacune de ces deux paires gagne ou perd une inversion. Le compte total varie donc de −2, 0 ou +2, et jamais d'un nombre impair. La position résolue en compte 0, une configuration avec un compte impair ne peut donc pas être atteinte. Prouver que toute position avec un compte pair est accessible constitue la partie la plus difficile : pour le taquin de 8, la recherche de la page le démontre directement.
Pourquoi un domino conserve la différence. Sur un échiquier, les voisines de chaque case sont de l'autre couleur. Un domino recouvrant deux cases adjacentes, il couvre donc une noire et une blanche. Poser des dominos ne modifie par conséquent jamais la différence entre les noires et les blanches parmi les cases découvertes. Un pavage terminé ne laisse rien à découvert, soit une différence de 0. Il nécessite donc une différence de 0 au départ : autant de cases d'une couleur que de l'autre.
Pourquoi au plus deux masses terrestres impaires. Suivez le parcours. Chaque fois qu'il traverse une masse terrestre, il arrive par un pont et repart par un autre. Les ponts d'une masse terrestre sont donc utilisés par paires. Les seules exceptions sont le point de départ, où un pont est utilisé pour partir, et le point d'arrivée, où un pont sert à arriver. Si le parcours s'achève là où il a commencé, chaque masse terrestre possède un nombre pair de ponts. Autrement, seuls le point de départ et celui d'arrivée en ont un nombre impair. La réciproque est également vraie lorsque les ponts relient tout, et la page trouve le parcours en construisant des boucles puis en les assemblant.

La moitié d'un taquin 3 × 3 ne pourra jamais être atteinte, et vous pouvez dire laquelle sans chercher 🖖

Cliquez sur 7 et 8 échangés et essayez de le résoudre. Comptez les paires de pièces qui se trouvent dans le mauvais ordre, en lisant ligne par ligne : ici une seule, le 8 avant le 7. Un glissement latéral ne modifie pas ce compte. Un glissement vertical fait passer une pièce par-dessus deux autres, modifiant le compte de 0 ou de 2. Ce nombre reste donc impair pour toujours, alors que la position résolue est à 0. La page a également exploré chaque position depuis la solution : 181 440 des 362 880 configurations sont accessibles. Ce sont exactement celles ayant un compte pair, et les deux plus éloignées nécessitent 31 coups. Le taquin de 15 a déferlé sur l'Amérique en 1880, et dans les années 1890, Sam Loyd a offert 1 000 $ à quiconque pourrait annuler l'échange du 14 et du 15. Un prix que personne ne pouvait espérer gagner.

Retirez deux coins opposés d'un échiquier et aucun pavage par dominos ne survit 🖖

Cliquez sur Coins opposés. L'échiquier complet peut être recouvert par 32 dominos de 12 988 816 manières. Découpez deux coins opposés et il ne peut plus du tout être recouvert : ces deux coins sont de la même couleur, il reste donc 30 cases d'une couleur contre 32 de l'autre, or chaque domino couvre une case de chaque. Si vous retirez plutôt les deux coins d'un même bord, un de chaque couleur, il y a 2 436 304 pavages. Cliquez ensuite sur Coin isolé : 30 et 30, un équilibre parfait, et pourtant toujours aucun pavage, car la case du coin n'a plus de voisin. Le compte des couleurs peut prouver qu'un échiquier est impossible à paver, mais il ne pourra jamais prouver l'inverse.

Le parcours de Königsberg échoue sur un calcul que vous pouvez faire de tête 🖖

Cliquez sur Königsberg. L'île possède 5 ponts et chacune des trois autres masses terrestres en a 3. Un parcours qui traverse chaque pont une seule fois arrive et repart de chaque masse terrestre qu'il traverse, utilisant ainsi ses ponts par paires. Ce n'est qu'aux points de départ et d'arrivée du parcours qu'un pont peut rester seul. Au maximum deux masses terrestres peuvent donc en posséder un nombre impair, et ici c'est le cas des quatre. Euler a résolu ce problème dans un article rédigé en 1735. Ajoutez un pont entre les deux rives avec le + situé à côté de B–C : il reste alors deux masses terrestres impaires, et la page trouve le parcours, de A à D. La somme de ces quatre comptes correspond toujours au double du nombre de ponts, c'est pourquoi les masses impaires vont toujours par paires.

Problème entièrement résolu

Quelqu'un pouvait-il gagner les 1 000 $ de Sam Loyd ? 4 étapes
Sur le plateau 4 × 4, échangez seulement le 14 et le 15, et laissez le trou dans son coin. Sam Loyd a offert 1 000 $ à quiconque parviendrait à le résoudre en faisant glisser les pièces. Était-ce possible ?

Ouvrez ce problème dans l'outil
1. Sur la grille 3 × 3 de cette page, l'invariant était la parité du nombre d'inversions :
  
  $3 wide: a vertical slide passes 2 tiles \Rightarrow Δ I \in {- 2, 0, + 2}$
2. Sur une grille de quatre de large, un glissement vertical fait passer une pièce par-dessus trois autres. Le compte varie donc d'un nombre impair, et le trou change de ligne :
  
  $4 wide: a vertical slide passes 3 tiles \Rightarrow Δ I \in {- 3, - 1, + 1, + 3}, Δ row = \pm 1$
3. Chaque mouvement inverse les deux parités ou aucune des deux. Leur somme, modulo 2, ne change donc jamais :
  
  $I + row of the blank (mod 2) never changes$
4. Comparez les deux positions, avec le trou sur la ligne 4 dans les deux cas :
  
  $solved: 0 + 4 = 4 (even), 14 \leftrightarrow 15 : 1 + 4 = 5 (odd)$
Réponse

Personne ne pouvait gagner : cet échange se trouve du mauvais côté de l'invariant. Exactement la moitié des 16! configurations, soit 10 461 394 944 000, peuvent être atteintes depuis la solution. Cliquez sur 7 et 8 échangés pour voir la version 3 × 3 de ce même piège.

$unreachable; \frac{16 !}{2} = 10, 461, 394, 944, 000 arrangements can be reached$

Parcours

Méthodes de démonstration

Références (3)

The parity argument for the 15-puzzle, the history (made in upstate New York in the 1870s, a craze in early 1880, analysed in the American Journal of Mathematics that year) and Sam Loyd's later $1,000 prize for a swap that cannot be done: K. Conrad, "The 15-Puzzle (and Rubik's Cube)", expository notes, University of Connecticut.
Euler's paper on the seven bridges of Königsberg, which reduced the walk to the number of bridges at each land mass: L. Euler, "Solutio problematis ad geometriam situs pertinentis", Commentarii academiae scientiarum Petropolitanae 8, 128–140 (written 1735, published 1741); Eneström number E53, The Euler Archive.
The number of domino tilings of square boards, with 12,988,816 for the 8 × 8 chessboard: OEIS Foundation, "A004003: Number of domino tilings (or dimer coverings) of a 2n X 2n square", The On-Line Encyclopedia of Integer Sequences.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.