Taquin et permutations
Publié le 15/05/2009

Lény Oumraou, Docteur agrégé de philosophie


Turing traite le cas du taquin en rappelant le résultat suivant :

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  :

1 -1 1 -1
-1 1 -1 1
1 -1 1 -1
-1 1 -1 1*

* = position initiale

Ainsi, si la case vide effectue n déplacements élémentaires successifs, la valeur correspondant à la position atteinte sera (-1)n. 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é A15, constitué des permutations paires du groupe symétrique de degré 15, S15.

Précisons que chaque configuration du taquin peut s'écrire dans la notation classique pour les permutations de S15  ; 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 A15 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 A15. 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 Sn.

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 An. 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.
- Il reste, dans un second temps, à montrer que tous les 3-cycles canoniques peuvent être obtenus à partir des règles du taquin. Pour cela, on repère des 3-cycles qu'il est particulièrement aisé d'obtenir sur le taquin, à partir de la configuration initiale, et on montre que chaque (1  2  i), pour 3 ≤ i ≤ 15, peut être obtenu à partir de ces 3-cycles. Ces derniers sont les 3-cycles « naturels », que l'on peut associer à chaque carré constitué de quatre cases sur la grille du taquin. On compte neuf de ces carrés. Appelons les les « carrés de quatre », pour ne pas les confondre avec les carrés élémentaires dont ils sont constitués. Pour obtenir un 3-cycle « naturel », il suffit de placer la case vide à l'intérieur du carré de quatre  correspondant, de déplacer les trois carrés restants, et de remettre la case vide, ainsi que les autres carrés, dans leur position initiale. Par exemple, dans la position standard,

 

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 ...

 

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 :

1 2 3 4
... 6 7 8
5 10 11 12
9 13 14 15

 

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

2 6 3 4
... 1 7 8
9 10 11 12
13 14 15 ...

 

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

2 6 3 4
5 1 7 8
9 10 11 12
13 14 15 ...

Supposons, maintenant, que l'on veuille obtenir (à partir de la position standard) le 3-cycle canonique (1  2  11). On devra commencer par mettre le carré 11 dans le carré de quatre [1; 2; 5; 6]. Pour cela, on supprime 10 du carré de quatre central [1; 7; 10; 11], puis on effectue les déplacements appropriés, de manière à obtenir :

1 2 3 4
5 11 ... 8
9 7 6 12
13 10 14 15

 

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

2 11 3 4
... 1 6 8
5 9 7 12
13 10 14 15

Il faut encore placer le carré 1 dans la position initiale du carré 11. Il suffit d'enlever 9 du carré de quatre central pour réaliser ce but :

2 11 3 4
5 6 7 8
9 ... 1 12
13 10 14 15

Il ne reste plus qu'à replacer les autres carrés dans leur position initiale :

2 11 3 4
-5 6 7 8
9 10 1 12
13 14 15 ...

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.

 

 
 
 
 
 
Dernières publications