Un casse-tête et son groupe

Quand les commutateurs permettent de résoudre un casse-tête de type Rubik’s Cube

Piste bleue Le 11 avril 2019  - Ecrit par  Romain Joly Voir les commentaires (2)

Il y a des mathématiques partout, même dans le Rubik’s Cube ! Avec l’aide d’une version très simplifiée de ce casse-tête nous allons découvrir les notions de groupe et de commutateur menant vers la résolution des casse-têtes de type Rubik’s Cube.

L’objet de cet article est un casse-tête que j’utilise pour des initiations à la théorie des groupes. Il a surtout servi pour des stagiaires de troisième ou seconde, mais aussi pour des interventions en classe entière. Ce casse-tête est composé de deux roues transportant chacune cinq éléments, un élément étant commun au centre, ce qui permet les échanges entre les roues, voir la photo en tête d’article ou la vidéo ci-dessous.

Pour mieux comprendre cet article, il vous sera très utile de pouvoir manipuler en direct le casse-tête. Vous devriez normalement pouvoir le faire grâce au programme javascript s’exécutant ci-dessous. Vous pouvez par exemple dupliquer la fenêtre de cet article et garder le casse-tête toujours visible pour le manipuler durant la lecture.

Le groupe du casse-tête

Les manipulations du casse-tête peuvent se décomposer en quatre opérations élémentaires :

  • $\rm G$ tourner la roue gauche d’un cran dans le sens horaire,
  • $\rm \overline G$ tourner la roue gauche d’un cran dans le sens anti-horaire,
  • $\rm D$ tourner la roue droite d’un cran dans le sens anti-horaire,
  • $\rm \overline D$ tourner la roue droite d’un cran dans le sens horaire [1].

Il est possible d’enchaîner plusieurs opérations élémentaires. Nous choisirons de noter $\rm G\,D$ l’enchaînement $\rm G$ puis $\rm D$, qu’il faudra donc effectuer dans l’ordre de lecture, de gauche à droite. Ainsi $\rm G\,D\, \overline{G}\,\overline{G}\, D\, D\, G$ code pour une suite d’opérations amenant le casse-tête de sa position de départ à la position

Ce qui va intéresser le mathématicien, c’est l’ensemble de toutes les opérations possibles, quelles sont ses propriétés et sa structure etc. Cette étude pourra sans doute nous mener vers une méthode de résolution de ce casse-tête... et si on la comprend bien, peut-être vers une méthode de résolution du Rubik’s Cube classique !

Qu’entend-on par « propriétés » de l’ensemble des opérations ? Par exemple, si on fait l’enchaînement $\rm G\,G\,G\,G$, alors c’est comme si on avait tourné la roue dans l’autre sens. On pourra donc noter $\rm G\,G\,G\,G = \overline{G}$. De même, $\rm D\,D\,D\,D\,D$ peut se simplifier en une opération plus simple : celle de ne rien faire. Nous allons noter cette opération $Id$ pour opération identité et donc dire que ${\rm D\,D\,D\,D\,D} ={Id}$. Ce genre d’égalité est une structure importante de notre casse-tête. Cette opération $Id$ paraît inutile, mais en fait elle est fondamentale pour nous. En effet, ce sera notre but à atteindre pour résoudre le casse-tête. Par exemple, mettons que l’on commence par mélanger le casse-tête en effectuant l’opération $\rm G$. Pour le résoudre, ce n’est pas très compliqué, il suffit de faire $\rm\overline G$ puisque ${\rm G\,\overline G}=Id$. C’est-à-dire que pour résoudre le casse-tête, il faut trouver l’opération revenant à l’identité. On dit que cette opération est l’opération inverse.

Petit exercice : quelle est l’inverse de la suite d’opérations $\rm G\, D\,\overline G \,\overline G \, D$ ? Autrement dit, comment revenir au départ si on a ainsi mélangé le casse-tête ? N’hésitez pas à tester votre solution sur l’applet javascript !

Dépliez la solution pour continuer à lire.

En général, le premier réflexe des élèves à qui j’ai posé la question est de dire qu’il faut faire $\rm \overline G \, \overline D\,G\,G\,\overline D$ puis d’attendre une validation par l’autorité du professeur. Mais, surprise, l’autorité du professeur n’a rien à voir là-dedans : il suffit de tester en vrai pour valider ou invalider la réponse scientifiquement. Le test conclut vite que la première intuition est fausse mais l’élève se rattrape rapidement et donne la bonne solution : $\rm \overline D \,G\,G\, \overline D\,\overline G$. En effet, il faut inverser les opérations mais aussi l’ordre des opérations. Il est intéressant de constater que l’on peut prouver qu’il s’agit de l’inverse juste par le calcul, en utilisant en série que $\rm \overline D\,D=Id$ etc. :
\[\rm G\,D\,\overline G\,\overline G \underbrace{D \,\overline D}G\,G\, \overline D\,\overline G = G\,D\,\overline G\underbrace{\overline G\,G}G\, \overline D\,\overline G = G\,D\underbrace{\overline G\,G}\overline D\,\overline G = G\underbrace{D\, \overline D}\overline G =\underbrace{G\,\overline G} = Id~.\]
Faire ce genre de raisonnement par écrit sans passer par la manipulation concrète du casse-tête, c’est avoir modélisé mathématiquement l’objet. On peut ainsi commencer à faire des mathématiques sur son fonctionnement en oubliant quel était l’objet de départ.

Résumons ce que nous savons sur notre structure des opérations pour notre casse-tête :

  1. nous avons des opérations élémentaires (un peu comme la multiplication par 2 ou par 3 pour les nombres)
  2. on peut composer des opérations pour en obtenir une nouvelle (un peu comme la multiplication par 2 puis par 3 donne une multiplication par 6)
  3. il existe une opération identité qui ne fait rien (comme la multiplication par 1 pour les nombres)
  4. chaque opération admet une opération inverse qui ramène au départ (comme la multiplication par 2 admet pour inverse la division par 2, qui n’est autre que la multiplication par 1/2).

Une telle structure est ce qu’on appelle un groupe. Le groupe de notre casse-tête a aussi certaines propriétés comme $\rm D\,D\,D\,D\,D=Id$ qui lui sont particulières (pour le Rubik’s Cube, il suffit de répéter quatre fois une opération élémentaire pour revenir au départ, et non cinq fois, son groupe est donc différent). On a aussi vu que l’ordre des opérations est important, par exemple on peut vérifier sur le casse-tête que $\rm D\,G$ et $\rm G\,D$ ne donnent pas le même mélange. On dit que notre groupe est non-commutatif, ce qui est inhabituel dans le monde mathématique que l’on voit avant le bac (par exemple multiplier par 2 puis par 3, c’est comme multiplier par 3 puis par 2 car la multiplication usuelle est commutative). Enfin, on peut noter que notre groupe est fini car il n’existe qu’un nombre fini de façon de réorganiser les pièces des roues [2].

Les commutateurs et les conjugaisons

Nous avons vu que le groupe des opérations du casse-tête n’est pas commutatif, c’est-à-dire que l’ordre des opérations est important. Dans un tel groupe, il y a des suites particulières d’opérations dont les mathématiciens et physiciens connaissent le rôle important : ce sont les commutateurs. On fait d’abord deux opérations, par exemple $\rm G$ et $\rm D$ puis leur inverses $\rm \overline G$ et $\rm \overline D$, le commutateur total étant donc $\rm G\,D\,\overline G\,\overline D$.

Que fait ce commutateur $\rm G\,D\,\overline G\,\overline D$ sur notre casse-tête ? Et bien il suffit d’essayer et l’on voit qu’il échange trois éléments de place. Ceci est très intéressant car on obtient un mouvement qui fait une opération simple sans changer le reste de notre casse-tête. Ce genre de mouvement forme la base de la résolution des casse-têtes « à la Rubik’s Cube » puisqu’il ne faut pas démonter les parties déjà finies quand on met en place les éléments qui restent à arranger. On peut tester plusieurs commutateurs à partir de nos opérations élémentaires.

$\rm G\,D\,\overline G\,\overline D$ $\rm D\,G\,\overline D\,\overline G$ $\rm \overline D\,\overline G\, D\, G$ $\rm \overline D\,G\, D\, \overline G$

Pouvez-vous trouver ce que font les autres commutateurs élémentaires comme $\rm \overline G\,\overline D\, G\, D$ simplement par la pensée ?

Déplier pour continuer la lecture

Il y a trois façons différentes d’anticiper ce que fait $\rm \overline G\,\overline D\, G\, D$. Tout d’abord, c’est l’inverse de $\rm \overline D\,\overline G\, D\, G$
et il fait donc tourner les trois mêmes éléments du centre-bas dans l’autre sens. On peut aussi dire que c’est $\rm \overline D\,\overline G\, D\, G$ mais en inversant la droite et la gauche et donc c’est l’opération symétrique par rapport à l’axe vertical. Enfin, on peut dire que c’est $\rm G\,D\,\overline G\,\overline D$
mais en tournant les roues dans l’autre sens, c’est-à-dire en inversant le haut et le bas et donc c’est son opération symétrique par rapport à l’axe horizontal. On obtient ainsi facilement les trois derniers commutateurs élémentaires à partir de $\rm \overline D\,G\, D\, \overline G$.

Une remarque pour les lecteurs connaissant les permutations

Nous voyons qu’utiliser un commutateur peut être une bonne idée pour obtenir des transformations agissant sur peu d’éléments. En fait, on peut écrire le résultat suivant. Si $p$ et $q$ sont deux permutations des éléments d’un ensemble et si leur supports ne se rencontrent qu’en un seul élément $e$, alors $q^{-1}\circ p^{-1}\circ q\circ p$ est simplement le 3-cycle $(e,q^{-1}(e),p^{-1}(e))$. La preuve est élémentaire puisqu’il suffit de suivre le voyage de chaque élément, la plupart revenant à leur place à la fin s’ils ne restent dans le support que d’au plus une des deux permutations. Si les supports se croisent en un petit nombre d’éléments, un raisonnement similaire montre que le support du commutateur n’est pas beaucoup plus grand (cf. photo en fin d’article).

Notons au passage que les commutateurs sont des combinaisons que l’on retrouve partout : en théorie des groupes, en mécanique quantique, en géométrie différentielle... mais aussi en conduisant. En effet, nous guidons notre voiture à l’aide de deux principaux mouvements : tourner les roues à droite (et son inverse, les tourner à gauche) et avancer un peu (et son inverse, reculer un peu). Ces mouvements peuvent se combiner (pour avancer beaucoup par exemple) mais ne commutent pas (avancer après ou avant avoir tourné les roues, cela change beaucoup de chose). Si on effectue leur commutateur, notre voiture a tourné un peu sur elle-même. En répétant plusieurs fois ce commutateur, nous arrivons à faire l’opération « demi-tour dans un espace étroit » qui ne faisait pas partie de notre arsenal de départ.

Plus compliqué maintenant, essayons de permuter trois éléments quelconques de notre casse-tête. Par exemple, comment obtenir la permutation ci-dessous ?

Indice pour la solution : se ramener à une situation vue plus haut...

L’idée est la suivante. Nous savons permuter trois éléments s’ils sont tous au centre. Nous allons donc d’abord amener nos trois éléments en position centrale pour pouvoir les permuter. Ce faisant, nous risquons de déplacer les autres pièces mais oublions ce problème pour le moment. Faisons par exemple $\rm \overline G\,D\,D\,G$ (on stocke deux éléments à gauche puis on amène l’élément à droite en place avant de ressortir les éléments de gauche). Puis nous effectuons notre permutation des trois éléments centre-haut déjà connue $\rm G\,D\,\overline G\,\overline D$. Enfin, il faut repositionner tout le monde comme au départ, nous faisons donc l’inverse de la première opération $\rm \overline G\,\overline D\,\overline D\,G$. Au total, l’opération cherchée peut donc se faire par
\[\rm \overline G\,D\,D\,G\, G\,D\,\overline G\,\overline D\,\overline G\,\overline D\,\overline D\,G\]
et il suffit de tester pour voir que cela marche. L’idée magique est la suivante. Nous avons certes dérangé les autres éléments en amenant nos trois éléments cibles au centre par $\rm \overline G\,D\,D\,G$. Mais les autres éléments ne sont pas affectés par le commutateur central $\rm G\,D\,\overline G\,\overline D$. Donc quand on fait l’inverse $\rm \overline G\,\overline D\,\overline D\,G$ de la première opération, les autres éléments reviennent à leur position de départ. Les seuls qui ont bougé sont nos trois éléments cibles qui ont été permutés par le commutateur central.

Cela peut commencer à paraître complexe, mais il suffit de bien décomposer le raisonnement et d’avoir un papier pour support. L’idée est donc de prendre en sandwich un mouvement connu par un autre mouvement et son inverse. En maths, cette structure est appelée conjugaison.

Une méthode de résolution

Mais revenons au problème de départ : comment résoudre efficacement notre casse-tête ? Notre analyse des commutateurs nous donne une méthode simple :

  1. placer correctement les quatre éléments extérieurs à 2 et 3 points. Cela se fait facilement sans se soucier du positionnement des autres éléments.
  2. utiliser les commutateurs élémentaires vus plus haut pour placer tous les éléments centraux. Encore une fois, l’avantage de ces commutateurs est de ne modifier que trois éléments sans déplacer les éléments déjà bien placés.

La vidéo du début de cet article présente l’étape finale. Les quatre éléments extérieurs sont bien placés et j’effectue deux commutateurs pour placer les éléments centraux.

Quelques compléments

Le casse-tête en chiffres
Le casse-tête a 181 440 positions différentes et si on le démonte et remonte au hasard, il y a une chance sur deux pour qu’on ne puisse plus le résoudre (les lecteurs les plus mathématiciens auront reconnu le groupe alterné sur 9 éléments). Toute position se résout en au plus 17 mouvements et il existe exactement deux positions qui demandent ces 17 mouvements, celle ci-dessous et son symétrique [3].

Une autre méthode de résolution
Si vous vous êtes attaqué au casse-tête avant de lire l’article, vous avez peut-être trouvé une méthode de résolution simple : placer un par un les éléments de façon directe et hop c’est fini. Cette méthode est évidemment trop simple pour se généraliser à d’autres casse-têtes, c’est pour cela que nous ne l’avons pas détaillé ici. Ceci dit, elle contient aussi un mystère mathématique : pourquoi marche-t-elle ? En effet, si on y fait attention, on place facilement un élément en utilisant deux autres éléments pour des placements intermédiaires. Donc on peut tout placer correctement, sauf deux éléments. Pourtant le casse-tête est toujours résolu ! Est-ce de la chance ? Non, car ces deux derniers éléments seront toujours bien placés : c’est un problème de signature de la permutation.
Le phénomène est le même pour le taquin standard : on ne peut pas permuter deux pièces sans bouger les autres. On pourra se reporter à l’article correspondant pour le taquin.

Le Pyraminx
Une fois la méthode de résolution décrite plus haut comprise, on peut facilement s’attaquer au Pyraminx qui est le Rubik’s Cube en forme de tétraèdre [4]. Les actions sur le Pyraminx consistent à tourner des étages d’éléments autour d’un des quatre axes du tétraèdre. Il se trouve que tourner juste la pointe n’est que cosmétique puisqu’on agit juste sur un seul élément et que celui-ci n’a besoin que d’être aligné avec l’élément juste sous lui. Au final, on n’agit sur le Pyraminx que par quatre opérations élémentaires consistant à tourner sur chacun des axes l’ensemble des deux petits étages de la pyramide au-dessus du troisième. Deux de ces opérations ne se croisent que sur un élément de type arête et donc leur commutateur échange simplement trois éléments sans changer le reste (voir image ci-dessous). De là, on place facilement tous les éléments à leur place mais il reste le problème de leur orientation, puisque les arêtes ont aussi un sens... je vous laisse y réfléchir et on peut en parler dans les commentaires.

Les structures des mouvements classiques du Rubik’s Cube
La façon répandue de résoudre le Rubik’s Cube classique est d’apprendre par cœur des suites de mouvements qui ont des actions particulières sur les éléments (les 12 arêtes et les 8 coins du cube). Bien sûr, il est important que ces suites de mouvements ne dérangent pas les parties déjà résolues du cube. Vous l’avez deviné, les structures en commutateurs et conjugaisons se retrouvent au centre de ces suites que l’on apprend par cœur sans comprendre. Retrouverez-vous les commutateurs et conjugaisons dans les mouvements suivants ? [5]

Orienter les arêtes sans modifier le reste : $\rm A\,D\,H\,\overline D\,\overline H\,\overline A$.

Quelle est la structure de cette combinaison ?

On reconnaît facilement le commutateur $\rm D\,H\,\overline D\,\overline H$
qui est pris en sandwich entre $\rm A$ et son inverse $\rm\overline A$. On a donc une conjugaison sandwichant un commutateur élémentaire.

Echanger trois coins sans modifier le reste : $\rm \overline G\,H\,D\,\overline H\,G\,H\,\overline D\overline H$.

Quelle est la structure de cette combinaison ?

Il s’agit d’un commutateur entre $\rm \overline G$ et l’opération $\rm H\,D\,\overline H$ qui est elle-même une conjugaison et qui a pour inverse $\rm H\,\overline D\,\overline H$.

Vers une résolution personnelle du Rubik’s Cube
Nous avons vu des exemples de mouvements à apprendre par cœur pour résoudre le Rubik’s Cube par la méthode traditionnelle. Mais on pourrait aussi chercher à découvrir sa propre méthode personnelle. La première piste est de partir de l’idée de commutateur. Si on fait le commutateur de deux mouvements de faces voisines, on modifie peu d’éléments : trois arêtes permutent et quatre sommets s’échangent deux à deux, les autres éléments restant en place. Comment utiliser ce mouvement élémentaire ? Nous en parlerons peut-être dans un prochain article...


Une photo avec trois casse-têtes de type Rubik’s : le Pyraminx, le cube classique et le Megaminx dodécaédrique. Pour chacun, on a effectué le commutateur de deux faces adjacentes. On voit que très peu d’éléments ont changé de place (3 pour le Pyraminx, 7 pour les deux autres). Comprendre l’action de ce commutateur conduit à des méthodes de résolution.

Post-scriptum :

L’auteur remercie chaleureusement Romain Dujardin pour l’édition de l’article,
Jean Fromentin pour l’aide technique, ainsi que Jérémy Le Borgne, projetmbc, Clément Caubel, Lison et Rémi Molinier pour leur relecture attentive .

Pour aller plus loin, le lecteur pourra consulter un article précédent très similaire et plus complet qui part d’une autre version simplifiée du Rubik’s Cube.

Des programmes javascript et python simulant le casse-tête ainsi que le fichier pour le découpage laser sont accessibles sur la page https://www-fourier.ujf-grenoble.fr/ rjoly/vulgarisation.html

Notes

[1Nous faisons ici le choix de reprendre les notations classiques pour le Rubik’s Cube, c’est-à-dire que l’opération inverse est noté par une barre et non l’exposant -1 (que les plus matheux me pardonnent). Par ailleurs, les disques droit et gauche ne sont pas orientés dans le même sens car c’est ce qu’il vient naturellement quand on manipule le casse-tête avec une main sur chaque roue.

[2Du coup, si on tourne les roues au hasard, on finira par résoudre le casse-tête mais cela risque d’être un peu long.

[3Merci à Samuel Gallay, un stagiaire en seconde à l’époque, pour avoir obtenu ce résultat par programme informatique !

[4oui, je sais, c’est un peu un oxymore...

[5Pour information, $\rm A$ veut dire « face avant », $\rm H$ « face du haut » et $\rm G$ et $\rm D$ codent encore pour « droite » et « gauche ». Il faut faire les mouvements dans le sens horaire quand on regarde la face.

Partager cet article

Pour citer cet article :

Romain Joly — «Un casse-tête et son groupe» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - Romain Joly
img_19810 - Romain Joly
img_19335 - Romain Joly
img_19336 - Romain Joly
img_19359 - Romain Joly
img_19355 - Romain Joly
img_19356 - Romain Joly
img_19357 - Romain Joly
img_19358 - Romain Joly
img_19362 - Romain Joly

Commentaire sur l'article

  • modèle dispo ?

    le 11 avril à 09:24, par olivierB

    bonjour,

    Je me demandais si le modèle du casse-tête était disponible ?
    Il me semble avoir été conçu à la découpeuse laser. Certains auraient peut-être envie de le reproduire s’ils en ont une dans un fablab voisin (ou via un service en-ligne).

    bien cordialement,
    olivierb

    Répondre à ce message
    • modèle dispo ?

      le 11 avril à 17:04, par Romain Joly

      Bonjour,

      Il y a un lien vers ma page en bas de l’article. On peut y trouver des fichiers, en particulier celui pour la découpe laser :
      https://www-fourier.ujf-grenoble.fr/ rjoly/Documents/Pedago/Vulgarisation/Rubik.svg
      Je ne garantis évidemment pas que le fichier soit compatible avec toutes les découpeuses...

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

L'auteur

Romain Joly