Mais dès 1879, dans l’American Journal of Mathematics, Johnson et Story démontraient l’impossibilité de cette version du jeu, à l’aide de la théorie des groupes. Ils utilisaient la toute nouvelle théorie des déterminants de James Joseph Sylvester, dont la partie intéressante ici se résume aux faits suivants :

• On peut représenter toute permutation des nombres de 1 à n par des composés de cycles (orbites des nombres ; en géométrie ce sont des rotations) ; par exemple le cycle amenant 1 sur 2, 2 sur 3 et 3 sur 1, se note (123) ;
• Les cycles les plus importants sont ceux d’ordre 2, appelés transpositions (géométriquement ce sont des symétries) ; en effet, toute permutation peut s’écrire (en général de plusieurs façons) comme produit de transpositions ; par exemple (123)=(12)(23) ;
• Quel que soit le produit de transpositions qui représente une permutation, la parité de leur nombre ne dépend que de la permutation (et non du produit choisi), et est appelée parité de la permutation ; par exemple (123) est paire puisqu’on peut l’écrire avec 2 (nombre pair) transpositions.
• L’ensemble des permutations paires est un groupe, le groupe alterné ; Il comprend la moitié des permutations.
• Les permutations du jeu de taquin sont toutes paires, et on ne peut pas par ces mouvements de jeu, passer d’une permutation impaire (comme 15-14) à une permutation paire (comme 14-15) : Loyd ne prenait pas un grand risque financier à promettre 1000$ au premier qui arriverait à réaliser l’impossible.

Cette théorie a été décrite par Édouard Lucas dans le tome 1 de récréations mathématiques, avec des généralisations à d’autres graphes que le damier 4×4 initial. Dans cet article, on va s’intéresser à des variantes du jeu, sur des graphes relativement simples, et se poser la question : Quelles sont les permutations que l’on peut atteindre à l’aide des mouvements du jeu ?

On verra notamment ce résultat surprenant :

• Si le graphe est bipartite (comme c’est le cas avec le graphe du jeu de taquin), le groupe de permutations qu’on peut obtenir est le groupe alterné ;
• Sinon, sauf exception, le groupe est le groupe symétrique (toutes les permutations peuvent être obtenues) ;
• mais il y a quelques exceptions, où le groupe obtenu est formé par des fonctions affines ou homographiques sur des espaces finis.

Si on se restreint aux positions pour lesquelles la case vide est celle en haut au milieu, il y a 120 permutations possibles des cartes, et le but du jeu est de revenir à celle indiquée sur la figure ci-dessus, que l’on va noter () puisqu’aucune carte n’a « bougé » avec cette permutation (la permutation (12345) étant un cycle dans lequel tout a bougé au contraire).

En déplaçant successivement les cartes 5,4,3,2,1,5 on se trouve avec ce tableau :

ce qui veut dire que le cycle (12345) peut être réalisé avec ce jeu. Ceci fournit 4 autres cycles qui sont les puissances de celui-ci, dans l’ordre des exposants, (13524), (14253), (15423) et (). Sa puissance 5^e étant l’identité, on dit que le cycle (12345) est d’ordre 5. On peut vérifier ça avec cette séance GAP :

c:=(1,2,3,4,5);
c*c;
c*c*c;
c*c*c*c;
c*c*c*c*c;

Où sont les 120-5=115 autres permutations sur les 5 cartes ? Si on clique successivement (à partir de la position d’arrivée) sur les cartes 3,2,1 et 3, on obtient un cycle plus petit :

Ce cycle est noté (123)(4)(5) ou plus simplement (123). Il est d’ordre 3, comme le montre GAP :

a:=(1,2,3);
a*a;
a^-1;

Mais en bougeant, à partir de la position d’arrivée, les cartes 3,4,5 et 3, on a un autre cycle d’ordre 3 :

En version GAP :

b:=(3,5,4);
a*b;
b^3;

En combinant les cycles c (d’ordre 5), a et b (d’ordre 3) de diverses manières, on trouve pas mal d’autres permutations possibles, par exemple le commutateur de a et b est un cycle d’ordre 3 (laissant 1 et 5 immobiles et faisant tourner 2, 3 et 4) :

a*b*a^-1*b^-1;

Mais tout cycle d’ordre impair est une permutation paire, et parmi les 120 permutations sur 5 élements, seule la moitié (les permutations paires) peut être atteinte par ces cycles a, b et c. On ne peut donc, comme pour le taquin traditionnel, avoir que 60 permutations maximum. Les a-t-on toutes ? Gap répond que oui :

g:=Group(a,b,c);
Size(g);

Le groupe formé par ces permutations est le groupe alterné à 60 éléments, c’est aussi le groupe des rotations laissant invariant un dodécaèdre : Le cycle c est une rotation de 72° autour de l’axe d’un pentagone, les cycles a et b sont des rotations autour d’un sommet : Vu du dessus, le triangle formé par les sommets voisins d’un sommet du dodécaèdre est équilatéral, et en le tournant de 120°, on laisse tout le dodécaèdre globalement invariant. Mais il y a aussi un cube dans cette histoire : Le Rubik’s Cube, lorsqu’on ne tourne que deux faces contigües (par exemple celle de devant et celle de droite, représentées respectivement par les carrés de gauche et de droite). Le Rubik’s Cube est d’ailleurs décrit par Berlekamp, Conway et Guy, comme une généralisation du taquin.

Le résultat cité ci-dessus laissait prévoir qu’il n’y aurait que 60 permutations dans ce jeu, parce que le graphe est bipartite, comme le montre cette coloration :

Chaque X ne touche que des O et chaque O ne touche que des X.

Le « lucky seven » est chanceux parce que, là, il y a 5040 permutations possibles, c’est-à-dire toutes les permutations des 7 cartes :

c:=(1,2,3,4,5,6,7);
a:=(1,2,3,4);
b:=(4,5,6,7);
g:=Group(a,b,c);
Size(g);

En fait la « chance » vient de ce que les cycles a et b, portant sur un nombre pair d’éléments, sont d’ordre impair, et permettent donc d’engendrer des transpositions.

On peut vérifier en jouant à ce fameux « lucky seven » que voici, dans un nouveau marais :

GAP permet de résoudre le lucky seven : Supposons qu’on soit arrivé à cette situation :

En général, il est assez facile d’arriver à cette situation, mais le plus dur reste à faire : échanger les cartes 6 et 7. On va dire à GAP que les cycles s’appellent a, b, et c (en fait on lui a déjà dit mais il faut transformer ces noms de variables en noms tout court), et lui demander quel mot écrit avec les lettres a, b et c (et leurs inverses) donne l’échange entre 6 et 7 :

gap> h:=EpimorphismFromFreeGroup(g:names:=["a","b","c"]);
[ a, b, c ] -> [ (1,2,3,4), (4,5,6,7), (1,2,3,4,5,6,7) ]
gap> PreImagesRepresentative(h,(6,7));
a^-1*c*b^-2*a^-1*c*b

On doit donc faire tourner les cartes de la moitié gauche dans le sens des aiguilles d’une montre, puis toutes les cartes (dans le sens direct), puis les cartes de la moité droite, deux fois, puis celles de la moitié gauche (sens des aiguilles d’une montre), puis toutes les cartes et enfin celles de droite (sens direct).

Comme dans les cas précédents, on peut utiliser l’espace vide (le « garage ») pour tourner les cartes de gauche ou celles de droite, ou encore on peut mettre une carte dans le garage pour faire tourner les autres et ainsi réaliser une permutation cyclique (d’ordre 5) laissant, in fine, fixe, celle qui avait été placée dans le garage.

Mais la particularité de ce jeu est que les permutations ainsi construites sont des fonctions homographiques sur le corps à 5 éléments. Ah vous vouliez du jeu sérieux vous êtes servis ! Donc, on regarde les restes de la division euclidienne par 5 (0,1,2,3 et 4) qui forment un corps parce que 5 est premier. En clair ça signifie qu’on peut effectuer une division sur ces 5 nombres parce que chacun a un inverse modulo 5 (2 et 3 sont inverses l’un de l’autre, 1 et 4=-1 sont chacun son propre inverse). Et une fonction homographique est donc de la forme (ax+b)/(cx+d) où le déterminant ad-bc est non nul. Alors on peut donner aux nombres 0,1,2,3 et 4 une structure de droite projective en leur ajoutant ∞ et en posant que si cx+d=0 alors l’image de x est ∞ et que l’image de ∞ est a/c, une fonction homographique peut être prolongée aux 6 éléments 0,1,2,3,4 et ∞.

Combien y a-t-il de fonctions homographiques sur cette droite projective à 6 éléments ? Il y a 5 choix possibles pour a, pour b, pour c et pour d, ce qui donne en tout 625 possibilités. Mais certains choix donnent la même fonction, comme x+1 et (2x+2)/2 (on remarque en passant que les fonctions affines sont considérées comme homographiques). En plus, il y a les cas où ad-bc=0, ce qui réduit assez considérablement le nombre de fonctions homographiques :

gap> g:=PGL(2,5);
Group([ (3,6,5,4), (1,2,5)(3,4,6) ])
gap> Size(g);
120

Il y a donc 120 fonctions homographiques sur le corps à 5 éléments (ça fait toujours son effet dans un dîner). Mais au fait, il y a aussi 120 permutations sur 5 éléments. Serait-ce à dire qu’une fonction homographique sur le corps à 5 élements ne serait qu’une permutation cachée ? De fait, oui, le groupe est exactement celui des permutations sur 5 élements. Et ce sont quoi, ces 5 éléments ? On a le choix entre des permutations qui ne sont pas des homographies, ou des groupes de Sylow... A priori, on pensait à plus simple : Les éléments 0,1,2,3 et 4 sont au nombre de 5, mais permuter ces éléments, c’est laisser fixe ∞, et une homographie laissant fixe ∞, c’est une fonction affine. Or des fonctions affines non constantes, il y en a 4×5=20 (4 choix pour a non nul, 5 choix pour b) sur le corps à 5 éléments. On est loin des 120. Mais certaines de ces fonctions sont faciles à « jouer », ce sont celles où le coefficient directeur est 1. Par exemple x+1 peut être jouée en cliquant successivement sur les cartes ∞ (pour la mettre sur le garage), puis 4, 3, 2, 1, 0, 4 et enfin ∞ (qui ressort du garage). GAP n’aimant pas les symboles non numériques comme ∞ ni même le 0, on va utiliser le nombre 6 pour représenter ∞ et le nombre 5 pour représenter 0. Le cycle d’ordre 5 ci-dessus est donc représenté dans GAP par (5,1,2,3,4). On le note ci-dessous c=x+1. Le cycle sur la moitié droite du graphe est a=(2x+3)/x et le cycle sur la moitié gauche est b=4x/(x+3). On peut maintenant composer ces permutations homographiques ; par exemple si on fait un tour sur la moitié droite puis un tour complet on applique d’abord la fonction (2x+3)/x puis la fonction x+1, ce qui donne (2x+3)/x+1=(3x+3)/x dont voici le tableau de valeurs :

On reconnaît la permutation (340∞) notée (3,4,5,6) par GAP (en entrant a*c on obtient bien ce résultat).

Voici une séance GAP qui peut aider à résoudre l’énigme des 6 risqués :

gap> c:=(5,1,2,3,4);
(1,2,3,4,5)
gap> a:=(5,6,2,1);
(1,5,6,2)
gap> b:=(2,6,4,3);
(2,6,4,3)
gap> g:=Group(a,b,c);
Group([ (1,5,6,2), (2,6,4,3), (1,2,3,4,5) ])
gap> Size(g);
120
gap> h:=EpimorphismFromFreeGroup(g:names:=["a","b","c"]);
[ a, b, c ] -> [ (1,5,6,2), (2,6,4,3), (1,2,3,4,5) ]
gap> PreImagesRepresentative(h,(4,5));
b*a^-1*b^-1*c
gap> PreImagesRepresentative(h,(3,4));
a^-1*b*a^-1*c*b
gap> PreImagesRepresentative(h,(2,3));
b*a^-1*b^-1
gap> PreImagesRepresentative(h,(4,6));
a^-2*b*a^-1*b^-2

Les solutions des jeux de type taquin utilisent souvent la possibilité de faire parcourir par la case vide, tous les sommets du graphe : C’est un parcours hamiltonien. Voici des jeux qui exploitent cette notion d’une autre manière, avec un joueur chargé d’établir un parcours entre deux parties du graphe, et un autre chargé d’empêcher l’établissement de ce parcours. On peut prouver qu’il existe une stratégie gagnante pour le premier joueur, mais elle est difficile à mettre en œuvre sans utiliser la notion d’arbre couvrant. Voici un parcours progressif, avec des graphes de taille croissante :

Rouge a trouvé comment gagner à coup sûr ? C’est le moment de voir s’il arrive aussi là-dessous :

Et là ?

Bravo, les rouges ! Mais là alors ?

Voici un jeu appelé Dodg’em, pour lequel une stratégie gagnante est connue (pour le premier qui joue) mais difficile à appliquer :

On peut généraliser ce jeu 3×3 à d’autres plateaux plus grands, par exemple le 4×4 :

Mais Conway a inventé une autre généralisation, à deux voitures par joueur, mais sur un plateau « semi-infini » (un quart de plan), qu’il a baptisé Dodgeridoo.

Dodg’em (le 3×3) est disponible sur Android, ainsi que diverses versions du taquin ou de l’âne rouge. Mais il y a des nouveaux jeux de ce genre basés sur les embouteillages, comme Rush Hour, lui aussi disponible sur Android, ou ce jeu de Dominique Valentin (qui se joue à seul joueur), jeu auquel un article est consacré sur MathemaTICE.

Un autre jeu similaire est celui des parkings, présenté ci-dessous, et créé récemment à La Réunion ; quelques différences séparent toutefois Dodg’em du jeu de parking :

• dans dodg’em, les voitures ne se contentent pas de se garer dans le parking final, elles sortent complètement du jeu ;
• dans le jeu des parkings, les voitures ont le droit de reculer ;
• dans le jeu des parkings, les destinations sont de part et d’autre du plateau, alors que dans dodg’em elles sont perpendiculaires ;
• dans le jeu des parkings, il est possible de bloquer complètement l’adversaire (et c’est même probablement la clé d’une stratégie gagnante).

Voici le jeu à jouer en ligne, le but étant d’arriver à la situation décrite sur l’image ci-dessous (à cliquer pour jouer en mode « plateau ») :

Et le même jeu, à imprimer pour jouer avec des pions (trois pions ou voiturettes de chaque couleur) :

Et le jeu à son début :

Suite au succès de ce jeu à la fête de la science 2016, voici le plateau de jeu tel qu’il a été tracé au moment de la conception du jeu (environ une minute pour dessiner ce graphe et énoncer les règles du jeu), au format pdf :

D’autres jeux sont stressants au sens où le gagnant est celui qui réussit à provoquer un embouteillage inextricable :

madelinette	fer à cheval

Les voici en action :

(embouteillage pour les blancs)

(embouteillage pour les noirs)