Le cube de Rubik est un support pédagogique très intéressant pour l’enseignement des mathématiques, en particulier pour la théorie des groupes.
La résolution du cube peut passer par l’algèbre, en modélisant chacune des rotations par une lettre. L’ensemble des configurations du cube constitue un groupe fini.
Une question fondamentale que l’on peut se poser sur le cube est le nombre minimal de mouvements nécessaires pour passer d’une position quelconque du cube à une autre. Un algorithme qui répondrait à cette question, en décrivant une méthode pour résoudre le cube à partir de n’importe quelle position initiale en un nombre minimal de mouvements, serait appelé « algorithme de Dieu ».
Cette question se décline en deux versions à propos du Rubik’s Cube, selon ce que l’on choisit d’appeler « mouvement élémentaire ». Si un mouvement élémentaire est un quart de tour d’une face du cube, étant donné une position, on peut faire 12 mouvements élémentaires. Si un mouvement élémentaire est au choix un quart de tour ou un demi-tour d’une face du cube, étant donné une position, il existe 18 mouvements élémentaires.
On savait jusqu'en 2010 que l’algorithme de Dieu nécessite au minimum 20 mouvements si on autorise les demi-tours, 26 sinon. Tomas Rokicki, mathématicien issu de l’université Stanford, a établi qu’il est possible de résoudre un Rubik’s cube en un maximum de 25 mouvements (en autorisant les demi-tours). Le même mathématicien a ensuite annoncé avoir réduit ce nombre à 22 avec de plus larges moyens matériels. En autorisant seulement les quarts de tour, il faut au maximum 40 mouvements (Tomas Rokicki annonce avoir réduit ce nombre à 29).
C'est finalement en juillet 2010 qu'un groupe de scientifiques internationaux (incluant Tomas Rokicki, ainsi que Morley Davidson, John Dethridge et Herbert Kociemba) démontre que le nombre de Dieu est 20 de manière certaine : en effet, il existe des configurations nécessitant 20 mouvements, mais la démonstration scientifique a confirmé que toutes les configurations possibles sont faisables en 20 mouvements ou moins. Cette découverte a nécessité quelques semaines de calcul distribués sur un grand nombre d'ordinateurs prêtés par Google, et représentant l'équivalent d'un temps de calcul de 35 ans sur un PC haut de gamme.
Aucun commentaire:
Enregistrer un commentaire