Le nombre de Dieu est 20

L

Je suis fier de vous annoncer aujourd’hui que depuis 2010, nous savons que le nombre de Dieu n’est ni 1, ni 3, ni 7, ni 42, mais exactement 20.

Qu’est-ce que le nombre de Dieu?

(CC-BY-SA http://commons.wikimedia.org/wiki/User:Booyabazooka)
(CC-BY-SA Booyabazooka)

Le « nombre de Dieu » est le nombre d’opérations de l’algorithme le plus efficace pour résoudre un problème. C’est une référence au mathématicien hongrois Paul Erdős (1913–1996), qui aimait évoquer « Le Livre », à savoir le livre (fictif) dans lequel Dieu aurait inscrit les preuves parfaites des théorèmes mathématiques. En effet, étant donné qu’un théorème peut être prouvé de différentes manières, ici seraient inscrites les démonstrations les plus belles. Accessoirement, Erdős était athée, et se référerait à Dieu en parlant du S.F. — le Suprême Fasciste — par exemple disant à ses amis: « je me suis fort bien remis de la grippe que le S.F. a cru bon de m’envoyer. »

Le terme « nombre de Dieu » a été inventé dans le contexte du rubik’s cube, et reste majoritairement associé à ce problème. La question est formulable ainsi: combien de mouvements sont nécessaires pour résoudre de la manière optimale n’importe quelle position du cube? Le nombre de mouvement est compté ici en métrique demi-tour (c’est à dire que chaque face tournée vaut 1, qu’elle ait été tourné d’un quart de tour ou d’un demi-tour). Grâce à la démonstration complétée en 2010, nous savons qu’il est possible, quel que soit la position du cube, de le résoudre en 20 coups ou moins. À titre de comparaison avec un sujet intéressant — moi —, il me faut en moyenne environ 90 coups pour le résoudre depuis une position non-triviale.

Bien entendu, il est extrêmement difficile de parvenir, en regardant le cube, à trouver une solution optimale — alors qu’il est très facile d’apprendre des algorithmes qui permettent de résoudre le cube en une centaine de rotations. Le record du monde1 de FMC (Fewest Moves Challenge) est toutefois détenu par Tomoaki Okayam, qui a résolu un cube en 20 mouvements au Czech Open 20122.

Comment ce nombre a été trouvé

On savait depuis 1995 que 20 était une limite inférieure du nombre de mouvements requis dans le pire des cas — c’est à dire qu’il y a des positions qui ne peuvent pas être résolues en moins de 20 coups. Mais est-ce que toutes les solutions peuvent être résolutions en 20 rotations? Il faut savoir que les nombre de positions de départ est de 43’252’003’274’489’856’0003. Pour donner une idée de l’ampleur de la chose, si l’on pouvait passer en revue un milliard de combinaison par secondes, il faudrait plus de 1’200 ans pour les visiter toutes. Ou encore, si l’on disposait de cubes de taille normale dans toutes les configurations possibles, on pourrait en recouvrir 275 fois la terre. Ce nombre est énorme, est la résolution n’est pas triviale.

En 2010, un équipe composée de Tomas Rokicki (programmeur de Palo Alto), Herbert Kociemba (prof de math de Darmstadt), Morley Davidson (mathématicien de Kent State University) et John Dethridge (ingénieur à Google) a pu passer en revue toutes les configurations, et montrer que chacune d’elle peut se résoudre en 20 coups ou moins. Et donc que le nombre de Dieu vaut 20.

La méthodologie a été la suivante:

  • Les 43’252’003’274’489’856’000 positions du cube ont été réparties en 2’217’093’120 ensembles de 19’508’428’800 configurations chacune. Ceci permet à chaque sous-problème de tenir dans la mémoire d’un PC moderne.
  • Le nombre d’ensemble a été réduit à 55’882’296 en utilisant des symétries et ensembles couvrants.
  • Les solutions recherchées n’étaient pas les optimales pour chaque position, mais celles de 20 mouvements ou moins — étant donné que la limite inférieure était déjà à 20 depuis 1995.
  • Un programme (code source) permet de résoudre chaque position (donc trouver le nombre de coup minimal) en 20 secondes environ.
  • 35 années de temps CPU offertes par Google on permis de trouver toutes les solutions.

Au final, il n’y a environ que 300 millions de solutions qui nécessitent au minimum 20 rotations, ce qui n’est pas beaucoup. En mélangeant le cube au hasard, il n’y a environ qu’un chance sur 10¹¹ de trouver une solution à 20 coups, et donc très probablement la configuration que vous tenez entre les mains se résout en 19 coups voire moins.

Update: ma méthode (simplifiée) pour résoudre le cube.


Petit quizz: est-ce que vous connaissez d’autres théorèmes mathématiques qui ont été démontrés à l’aide d’ordinateurs?

Accessoirement, cela pose des questions intéressantes sur la validité des preuves informatiques. Peut-être pour une prochaine fois.

  1. Une vidéo de certains records de rubik’s cube. Celle de Tomoaki Okayam n’y est malheureusement pas. Et la liste de tous les records actuels.
  2. À noter qu’il se peut que le cube qu’il tenait entre les mains aurait pu être résolu en moins de mouvement.
  3. Le nombre est trouvé ainsi: (1/12) · 12! · 8! · 212 · 38.
close

Abonne-toi pour ne pas manquer les prochains articles !

Abonne-toi pour ne pas manque les prochains articles :

4 commentaires

  • Excellent! J’adore le mélange de math, de Dieu et de programmation 🙂 Bravo quand même au sujet lambda d’y arriver en 90 coups, moi je pense que je balance le cube par la fenêtre bien avant 90 coups!

  • Et pour répondre à la question des théorèmes démontrés par ordinateur, peut-être celui des 4 couleurs.

    D’autre part, et bien que ce ne soit pas un théorème, je pense que l’informatique (et Internet en particulier) a largement contribué à prouver la Loi de Murphy, que je cite souvent en termes de sécurité informatique. Pour ce qui est du parallèle théologeek, je te laisse y réfléchir (sous la douche ou en fumant une pipe). 🙂

    • Effectivement, le théorème des 4 couleurs et le plus célèbre, car il a crée un peu de remous — est-ce qu’on peut accepter une preuve à laquelle a contribué un ordinateur? 

      Et oui, il y a de quoi faire quelque chose sur la Loi de Murphy, je vais y réfléchir 🙂

      Merci Micaël !

Abonne-toi

Pour ne pas manquer les prochains articles :

Catégories

Ici on parle de…