Théorème : Soient α et β deux configurations du taquin dans lesquelles la case vide est placée en même position. Alors β est accessible à partir de α ssi β est une permutation paire de α.

On montre l'équivalence en deux étapes ; la partie triviale est :

1. Si β est accessible à partir de α, alors β est une permutation paire de α. 

Preuve : en principe, ce sont les carrés que l'on déplace. Mais on peut s'intéresser aux déplacements correspondants de la case vide. Associons le nombre 1 à la position initiale de la case vide, et convenons qu'à chaque déplacement élémentaire elle change de signe. Comme elle ne peut se déplacer que verticalement, et horizontalement, dans les cases adjacentes, on peut associer à chaque case des valeurs fixées par le parcours de la case vide, indépendamment de l'ordre chronologique de ce parcours. Ces valeurs sont réparties en damier, c'est-à-dire que deux cases adjacentes n'ont jamais la même valeur. Par exemple, si la position initiale de la case vide est la case la plus basse, et la plus à droite (comme dans la position standard), on obtient la répartition  :

 * = position initiale

Ainsi, si la case vide effectue n déplacements élémentaires successifs, la valeur correspondant à la position atteinte sera (-1)ⁿ. Par suite, la valeur associée à la position atteinte est 1 ssi n est pair (i.e. la case vide a effectué un nombre pair de déplacements élémentaires). D'où l'on peut conclure que si la case vide revient à sa position initiale, ce ne peut être qu'après un nombre pair de déplacements élémentaires, puisque la valeur correspondant à cette position est 1.

Maintenant, il est facile de voir que chaque déplacement élémentaire du taquin est une permutation de deux cases, l'une des deux cases étant la case vide. Toute configuration atteinte, avec la case vide revenue à sa position initiale, est donc une composition d'un nombre pair de transpositions, c'est-à-dire une permutation paire.

La démonstration de cette première implication fait un usage caché de la notion algébrique de signature d'une permutation. Le recours à l'algèbre est moins discret dans la preuve de la réciproque.

2. Si β est une permutation paire de α, alors β est accessible à partir de α.

Rappelons que, par hypothèse, la permutation laisse invariante la position de la case vide. On peut donc considérer qu'il s'agit d'une permutation des quinze carrés. Dans la mesure où elle est supposée paire, on s'intéresse au groupe alterné de degré 15, noté A₁₅, constitué des permutations paires du groupe symétrique de degré 15, S₁₅.

Précisons que chaque configuration du taquin peut s'écrire dans la notation classique pour les permutations de S₁₅  ; ainsi :

représente la configuration où la première case (en circulant de gauche à droite et de haut en bas) est occupée par le carré numéroté σ(1), et de façon générale, la  ième case est occupée par le σ(i)^ème carré (1 ≤ i ≤15). Il est donc tout à fait légitime de traduire la question sur le taquin par une question d'algèbre.

Il s'agit en fait de montrer que tous les éléments du groupe A₁₅ peuvent être obtenus par des déplacements autorisés par les règles du taquin. La difficulté est de lier les déplacements « physiquement » possibles du jeu aux éléments de A₁₅. Dans cette perspective, un résultat classique d'algèbre est particulièrement utile :

Lemme : le groupe alterné de degré n est engendré par les cycles de longueur 3 de S_n.

Avec ce lemme, il ne reste plus qu'à démontrer que tous les 3-cycles peuvent être obtenus à  partir des règles du taquin. C'est là une étape décisive, mais tout n'est pas encore réglé. Car comment montrer que tous les cycles de la forme (i  j  k) peuvent être ainsi obtenus ? La généralité même de cette forme ne rend pas aisée l'entreprise. Mais l'algèbre vient encore à notre secours : on peut montrer, en effet, que les 3-cycles (1  2  i), 1 ≤ i ≤ n suffisent à engendrer le groupe A_n. Dans le cas qui nous occupe, cela revient à procéder en deux étapes :

- On commence par montrer que tout 3-cycles (i  j  k) est un produit de 3-cycles de la forme plus particulière (1 2 h), que nous qualifierons de canonique. Cette étape est encore purement algébrique, et ne fait pas référence aux possibilités du taquin.

les carrés 1, 2, 5, 6 constituent un carré de quatre (appelons  le [1; 2; 5; 6]). Pour construire le 3-cycle (1  2  6), on « enlève » le 5 de ce carré de quatre :

puis on place les trois carrés restants dans la position voulue :

Enfin, on remet les autres cases dans leur position de départ :

Puis on enlève 5 du carré de quatre [1; 2; 5; 11] ainsi formé, et l'on déplace les carrés restants :

On se convaincra aisément que le même type de procédé peut être utilisé pour obtenir tous les 3-cycles canoniques (il y a treize vérifications à effectuer).

Cela achève la preuve du théorème.

Retour au Sommaire

Retour à l'article