Rubik's Cube Mathématique

En 2010, une équipe internationale de chercheurs a prouvé que quel que soit le degré de brouillage d'un Rubik's cube, il ne faudrait pas plus de 20 mouvements pour le résoudre. Leur preuve, cependant, reposait sur l'équivalent de 35 ans de calcul numérique sur un bon ordinateur moderne.

Pour les cubes plus gros que le Rubik's cube standard, une prospection adéquate des positions de départ peut bien dépasser la capacité de calcul de tous les ordinateurs du monde. Mais en septembre, Erik Demaine (à droite), professeur agrégé d'informatique et d'ingénierie, a dirigé une équipe comprenant son père, le professeur invité du CSAIL Martin Demaine (à gauche), qui a démontré la relation mathématique entre le nombre de carrés dans un cube et le nombre de coups dans la solution la plus courte à son état le plus brouillé.

La façon standard de résoudre un Rubik's cube est de trouver un carré qui n'est pas en position et de le mettre en place tout en laissant le reste du cube aussi peu modifié que possible. Cela donne une solution dans le pire des cas dont le nombre de mouvements est proportionnel à N2, où N est le nombre de carrés par ligne. Mais l'équipe a vu que dans certaines circonstances, une seule séquence de torsions pouvait déplacer plusieurs carrés en place.

Décrire ces circonstances mathématiquement n'était pas une tâche facile. Dans la première heure, nous avons vu qu'il devait être au moins N2/log N, dit Erik Demaine. Mais ensuite, il a fallu plusieurs mois avant que nous puissions prouver que N2/log N était assez de mouvements.

cacher