lundi 1 novembre 2010

Cube Rubik en 2 temps, 20 mouvements

Partager



Pour Monsieur A.



Symbole culturel de la grande intelligence, le cube de l'architecte hongrois Ernö Rubik est né en 1974 pour devenir dans les années 80 le casse-tête le plus populaire du monde. Peut-être est-ce parce que, comme son auteur le prétend, ce cube 3x3 est la représentation de la vie, des trilogies mère-père-enfant, eau-terre-air, ciel-purgatoire-enfer, la naissance-la vie- la mort. Quoiqu'il en soit, il est devenu le symbole culturel de l'intelligence supérieure.




Plus de 350 millions de cubes auraient été vendus partout dans le monde. Évidemment, l'algorithme de résolution a vite été diffusé, question d'avoir l'air intelligent ! Le plus populaire est celui de Lars Petrus. Mais plus rapide encore, la méthode des coins du montréalais Gaétan Guimond. Avec la méthode de Guimond (1982), le cube peut être complété après une cinquantaine de mouvements.

Les concours peuvent commencés. Guiness, le cube à une main, les yeux bandés, sous l'eau, avec les pieds... C'est le hollandais Erik Akkersdijk qui détient le record, ayant réussi le cube en 7,08 s en 2008.




Bof... lorsqu'il est question de temps, il y a toujours moyen de tricher !



Intéressons-nous plutôt aux mouvements.

Dès sa sortie mondiale en 1981, comme le prétendait Guimond, le mathématicien anglais Morwen Thistlethwaite a démontré que le cube pouvait être refait en moins de 51 mouvements.

Dix ans plus tard, on démontrait qu'il était possible de le faire en moins de 42 mouvements.

Puis, depuis 2008, le programmeur californien Tomas Rokicki s'est attaqué à l'affaire pour découvrir ce qu'il a appelé le nombre de Dieu : 20.

Comment ont-ils fait ?

Ce sont des programmeurs.
(La question que l'on ose : les mathématiciens ne seront-ils pas un jour obligés de trouver jolies ces démonstrations informatiques ?)

Ils ont donc considéré les 43 252 003 274 489 856 000 arrangements possibles sur le cube. Ils les ont divisés en 55 882 296 ensembles distincts (ils ont enlevé les recouvrements et les arrangements symétriques), puis, ils ont considéré les algorithmes permettant de résoudre le cube en 20 mouvements ou moins.

Il faut noté que Rokicki avait démontré en 2008 que le cube pouvait être fait en moins de 22 mouvements.

Ils ont ensuite programmé le tout et fait roulé le programme sur les 55 882 296 ensembles.

Après 35 ans de temps de processeur, ils ont obtenu une solution pour tous. Le cube peut donc être résolu en moins de 20 mouvements.

Mais est-ce le vrai vrai minimum ?

Les détails sont ici.

Enfin... pour ceux qui aiment se casser la tête.

2 commentaires:

Dr. Goulu a dit...

"Mais est-ce le vrai vrai minimum ?"

après avoir lu http://cube20.org/ je pense que oui, car ils ont montré il y a assez longtemps que certaines positions de départ nécessitaient exactement 20 mouvements, et ce qu'ils viennent de faire est de montrer que toutes les autres positions peuvent être résolues en moins de 20.

"les mathématiciens ne seront-ils pas un jour obligés de trouver jolies ces démonstrations informatiques ?".

C'est plus une preuve expérimentale qu'une démonstration, à mon avis. Je pense qu'une preuve nécessitant 35 ans de CPU n'est pas belle, mais peut donner des idées aux mathématiciens pour la réduire une jour à une page de formules...

Missmath a dit...

J'aime votre commentaire. J'ai toujours aussi considérer une preuve expérimentale n'était pas une démonstration. Jusqu'à ce que Gilbert Labelle, mathématicien bien connu de l'UQÀM, en prenne la défense. Son plaidoyer m'a bouleversée ! Mais bon, comme je suis vieille, ces preuves, je veux bien les tolérer, mais de là a les trouver jolies, oh que non !