Cet article est destiné au grand public. Sa construction circule en permanence entre théorie et pratique. Les notions introduites et développées sont celles d’une licence de mathématiques.

L’objet de cet article est la modélisation mathématique de deux jeux : d’une part, le Rubik’s cube et d’autre part, son petit frère « aplati », le Taquin à retournement. Cette modélisation a un double objectif :

1. Dégager la structure mathématique de chacun de ces deux jeux et proposer des outils de recherche et d’analyse de mouvements afin que le lecteur en assimile les intérêts spécifiques et puisse ensuite élaborer de lui-même une méthode de résolution. Et l’étude exhaustive du Taquin nous permet d’appréhender bien plus finement les problématiques du Rubik’s cube.
2. Utiliser ces jeux pour contextualiser des notions théoriques d’algèbre structurale, en faisant de ces jeux des supports pédagogiques pour introduire ces notions et en illustrer les principes fondamentaux. Il s’agit par là-même d’en illustrer l’intérêt de manière convaincante.

Introduction

Chacun a, un jour ou l’autre, tenu dans ses mains un Rubik’s cube. Cet objet a été créé en par l’architecte et designer hongrois Ernö Rubik. Sa résolution, c’est-à-dire la réorganisation par couleur de chacune des faces en composant des rotations d’un quart de tour de ses faces sur elles-mêmes dans le sens trigonométrique, que nous appellerons dans la suite « mouvements élémentaires », peut de prime abord sembler simple ; mais on se rend vite compte qu’en voulant ordonner tel sommet ou telle arête, on dérange d’autres parties du cube. Lorsque l’on se procure un Rubik’s cube, il est fourni un « mode d’emploi », c’est-à-dire un algorithme qui permet de réorganiser les couleurs en plusieurs étapes. Apprendre par cœur les méthodes de ce « mode d’emploi » présente certes l’avantage de savoir résoudre efficacement le cube, mais aussi l’inconvénient majeur de ne pas s’être réellement confronté à ses difficultés, ignorant en fait essentiellement ses mystères, mystères que nous allons dévoiler en modélisant mathématiquement le Rubik’s cube.

Dans la première partie, nous verrons que les mouvements qui permettent de passer d’un état, appelé configuration, à un autre, peuvent se traduire mathématiquement par l’action d’un groupe sur l’ensemble de ces configurations possibles. On construit alors une structure de graphe dont les sommets sont ces configurations. Ces sommets sont liés par une arête si on peut passer de l’un à l’autre par un mouvement élémentaire. La résolution de notre Rubik’s cube en un nombre minimal de coups, dont on abordera la problématique, amène à la recherche d’un chemin de longueur minimale dans ce graphe menant d’une configuration à la configuration résolue.

L’intérêt de l’étude du Taquin à retournement, objet plus simple mais aux propriétés très similaires, apparaîtra au fil de la lecture de la seconde partie. En effet, nous allons pouvoir trouver ce chemin minimal pour le Taquin à retournement. Cela nécessitera une étude plus fine et plus aboutie de l’action d’un groupe opérant sur un ensemble. L’action du groupe des symétries du carré nous permettra de restreindre l’ensemble des configurations à considérer. On pourra ainsi résoudre le problème de la recherche d’un chemin minimal sur un graphe plus petit.

Les notions mathématiques qui sont développées dans cet article, et qui découlent naturellement de l’étude de ces deux objets, sont plus précisément les suivantes :

1. Groupes :
   1. Notions de groupe, de sous-groupe, de relation d’équivalence, de sous-groupe distingué, de groupe quotient, de groupe engendré par un élément et d’ordre d’un élément, d’isomorphisme.
   2. Action d’un groupe sur un ensemble : orbite, stabilisateur, opérations libre et transitive, formule des classes.
   3. Groupes symétriques, groupe diédral du carré.
       
2. Graphes :
   1. Configurations voisines, graphe et structure d’espace métrique associé.
   2. Recouvrement d’un graphe par des boules de rayon donné, sous-graphe des centres des boules et fluidité du trajet en passant par les arêtes de ce sous-graphe.
   3. Deux algorithmes de minimisation du trajet dans le graphe du taquin.

Les niveaux d’enseignement visés sont les deuxième et troisième années universitaires. Les généralités sur les groupes, le groupe engendré par un élément et le groupe symétrique sont du niveau licence 2. Les opérations d’un groupe sur un ensemble, le groupe diédral et la théorie des graphes peuvent être vus en licence 3. Cependant, ces notions mathématiques sont définies dans l’article afin qu’il soit, autant que faire se peut, accessible à un élève de Terminale scientifique qui suit la spécialité mathématique. Cet article est aussi destiné aux lecteurs désireux de découvrir ou d’approfondir des notions de base de mathématiques dans un contexte ludique et surprenant.