UQAM - Université du Québec à Montréal
Entrevues
UQAM › Entrevues › L'énigme du cube Rubik
Micro

François Bergeron.
Photo: Michel Giroux.

L'énigme du cube Rubik


Par Dominique Forget

7,08 secondes. C'est le temps qu'a mis le Hollandais Erik Akkersdijk pour résoudre un cube Rubik au dernier championnat du monde. Un record! Le Polonais Rafal Guzewicz l'a fait les yeux bandés en 54,22 secondes. Quant au Coréen Lee Seung-Woon, il a complété le casse-tête avec une seule main. Chronomètre : 14,34 secondes.

Depuis la frénésie des années 1980, le fameux cube inventé par le sculpteur et architecte hongrois Erno Rubik a acquis un statut de célébrité. Plus de 300 millions d'exemplaires ont été vendus dans le monde. Selon un sondage mené récemment par la firme britannique eBid, le cube remporterait la première place au palmarès des jouets cultes. Devant le célébrissime yo-yo.

Chaque année, les cubers (adeptes du cube) se donnent rendez- vous dans l'espoir d'épater la galerie. Des sites Internet entiers sont dédiés aux astuces qui permettent d'aligner le plus rapidement possible les faces de même couleur.

Mais il n'y a pas que les cubers qui sont passionnés par le cube. Les mathématiciens qui se spécialisent en combinatoire - une discipline qui étudie les combinaisons possibles d'objets finis dans l'espace - s'intéressent aussi au jouet. Leur question : quel est le nombre minimum de mouvements qu'un joueur doit exécuter pour remettre en ordre un cube parfaitement mélangé?

Théorie des groupes

«Si l'on prend un cube en ordre et qu'on mélange les couleurs en exécutant 30 rotations, par exemple, on sait qu'on pourra le remettre à son état d'origine en 30 mouvements, en revenant sur ses pas», explique François Bergeron, professeur au Département de mathématiques et directeur du Laboratoire de combinatoire et d'informatique mathématique (LACIM). «Ça ne veut pas dire pour autant qu'on ne pourrait pas résoudre le cube en moins de 30 rotations. Il y a peut-être une solution plus rapide.»

Un programme informatique pourrait-il bêtement tester toutes les configurations du cube et les chemins possibles pour les résoudre? Ce n'est pas si simple. Le cube n'offre pas moins de 43 milliards de milliards de configurations possibles! Si l'on empilait un par-dessus l'autre des cubes représentant chacune de ces configurations, la tour s'élèverait jusqu'au Soleil, puis reviendrait sur Terre... 8 millions de fois. Ce n'est pas tout. Il existe, pour chacune de ses configurations, 12 mouvements qui peuvent l'altérer.

«Pour résoudre le problème, il faut faire appel à la théorie des groupes», explique François Bergeron. Cette théorie permet de s'attaquer à des problèmes en exploitant leurs symétries. Elle sert, en quelque sorte, à transformer des problèmes complexes en problèmes plus simples. «On arrive à systématiser la découverte de suites de mouvements qui simplifient le problème», résume le mathématicien.

30 000 ordinateurs

Depuis des années, des mathématiciens-informaticiens travaillent donc à simplifier le problème. Mais ils sont encore loin du but. Le dernier algorithme qu'ils ont mis au point est si complexe qu'il faudrait environ 30 000 ordinateurs pour le résoudre. Les ordinateurs les plus rapides au monde, ceux du Lawrence Livermore National Laboratory, pourraient y arriver en 38 jours. Mais il est loin d'être acquis, pour ne pas dire impossible, que le Département de l'énergie des États-Unis prête son joujou pour s'attaquer à un tel problème.

Pourtant, l'énigme est prise au sérieux par les mathématiciens. François Bergeron ne se penche pas sur ce problème spécifique, mais l'un des théorèmes qu'il a mis au point, en collaboration avec ses collègues, a permis de répondre à une question similaire : combien de fois faut-il couper un paquet de cartes pour qu'il soit parfaitement mélangé? La réponse après moult calculs : sept fois.

«Cela peut sembler futile, mais ce qu'on vise en fait, avec la combinatoire et la théorie des groupes, c'est de développer des outils mathématiques qui serviront à expliquer le monde qui nous entoure, explique François Bergeron. Il serait inutile de commencer à dresser la liste de tous les phénomènes observables. On a besoin de concepts mathématiques qui permettent de formuler de grandes lois générales.»

Après le paquet de cartes, le cube Rubik? Et puis la structure globale de l'univers, pourquoi pas?

Séparateur

Source : Journal L'UQAM, vol. XXXV, no 6 (10 novembre 2008)

Catégories : Sciences, Professeurs

Séparateur

Flèche Haut

UQAM - Université du Québec à Montréal  ›  Mise à jour : 10 novembre 2008