Permutations et pavages

vendredi 25 novembre 2016
par  Alain BUSSER

Le jeu de taquin a été créé par le truculent Sam Loyd (du moins selon Loyd lui-même) et a d’emblée eu un grand succès aux USA dans les années 1870. Le principe de ce jeu évoque celui de l’Âne rouge (jeu d’origine thaïlandaise ou française, à moins que ce soit un jeu inspiré par le taquin ?), parce que

  • on joue seul (« solitaire » en français, « puzzle » en anglais) ;
  • chaque coup consiste à déplacer une des pièces du jeu, par translation, vers l’emplacement vide. Sam Loyd proposait 1000$ à qui réussirait, avec de tels mouvements, à échanger les positions du 14 et du 15.

Histoire

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 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, sa parité ne dépend que de la permutation (et non du produit choisi), et est appelé parité de la permutation ; par exemple (123) est paire puisqu’on peut l’écrire avec 2 (nombre impair) 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 ds 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.

Pour Édouard Lucas, le jeu de taquin généralisé (qu’il appelle continental parce qu’il y a des continents et des presqu’îles servant de garages) est un jeu sérieux sur la théorie de Galois, à en juger par cette description :

Découvrir les groupes de permutation et leur énervante non-commutativité en jouant avec des cartes ? Pourquoi pas ? On va essayer, mais en s’aidant du logiciel GAP qui est spécialisé dans la théorie des groupes finis.

On va commencer par un exemple simple, un jeu de taquin à 3×2 cases (au lieu du 4×4 classique), la case vide étant initialement au milieu de la rangée du haut :

HTML - 4.4 ko

Il s’agit d’un jeu en ligne, que l’on peut ouvrir dans le navigateur pour y jouer un peu. Le plateau de jeu représente un étang surmonté de pontons que l’on emprunte pour déplacer les cartes.

Combien de permutations ?

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 :

5 4
1 2 3

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 5e é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 :

3 5
1 2 4

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 :

1 3
2 4 5

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 :

O X O
X O X

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

De 5 à 7

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 :

HTML - 281.5 ko

Solution

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

1 * 6
2 7
3 4 5

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).

Les 6 risqués de Ricky

Ce jeu a été nommé par Conway, en hommage à Richard Wilson, qui est l’auteur du résultat sur le lien entre graphes bipartites et nombre de permutations, et de cette variante où il y a 120 permutations sur les 720 permutations des 6 cartes laissant vide le garage central :

HTML - 276 ko

Si on mélange totalement au hasard les cartes, on a donc une chance sur 6 de pouvoir résoudre le jeu, d’où le nom de « risqué ».

Homographies

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 :

x 0 1 2 3 4
3+3/x 1 2 4 0 3

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

Après avoir dangeureusement transporté des cartes numérotées sur des pontons au-dessus du marais, voici un autre jeu où il est question de mangroves, à terraformer. Au départ du jeu il y a des toutes petites rivières allant d’un bord à l’autre (une seule carte, par exemple le coin en bas à droite), et des petites rivières n’occupant que deux cartes. Le premier joueur qui complète une rivière d’au moins trois cartes allant d’un bord à un bord, a gagné :

HTML - 36.3 ko

Ce jeu a été créé par Lewthwaite, probablement comme une variante de ce jeu :

HTML - 1.7 ko

Pour cette version, Berlekamp, Conway et Guy ont trouvé une stratégie gagnante (pour le second joueur) basée sur un pavage des 24 cases non centrales par des dominos.

Parcours hamiltoniens

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 :

HTML - 3 ko

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

HTML - 3.8 ko

Et là ?

HTML - 4.8 ko

Bravo, les rouges ! Mais là alors ?

HTML - 6 ko

Circulation aux heures de pointe

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

HTML - 35.2 ko

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

HTML - 35.9 ko

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 ») :

HTML - 33.1 ko

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

PDF - 132.6 ko

Et le jeu à son début :

JPEG

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 :

PDF - 62.6 ko

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

madelinette fer à cheval
PDF - 172.2 ko
PDF - 135.9 ko
HTML - 3.3 ko
HTML - 2.9 ko
fer à cheval
Jeu décrit par Édouard Lucas

Les voici en action :

JPEG

(embouteillage pour les blancs)

JPEG

(embouteillage pour les noirs)


Bonus :

Pour jouer au jeu « lucky seven » sur Android, voici un installeur :

Zip - 1.5 Mo
installeur du jeu « lucky seven » pour Android

Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6


Brèves

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 22 mai 2017

Publication

745 Articles
Aucun album photo
131 Brèves
11 Sites Web
127 Auteurs

Visites

49 aujourd'hui
1130 hier
2021175 depuis le début
7 visiteurs actuellement connectés