Problèmes mathématiques autour des cubes

Vos questions / remarques sur le cube classique 3x3x3
Les méthodes principales du 3x3x3 et leurs variantes
Les visiteurs peuvent poster des messages dans cette partie
7 messages Page 1 sur 1
T-Tel


Bonjour,

Je me demandais si vous aviez des sites convenables sur les mathématiques derrières les cubes Rubik. Contenant des problèmes et leurs preuves.

Mon niveau en mathématique est bon (niveau License informatique), mais pas extraordinaire. Je me demande par exemple quelle est la preuve mathématique (si elle existe) derrière l'affirmation "Quelle que soit l’algorithme, s'il est exécuté en boucle, on retombera toujours sur la configuration originelle". Ou encore des questions du style "Quel est le plus court algorithme permettant de passer par l’ensemble des configurations d'un rubik's Cube"

J'ai cherché un peu mais pas moyen de tomber sur un site correspondant suffisamment a ce que je recherche :/
Philfully
VIP au club des 1000
Messages : 2352
Enregistré le : mer. nov. 11, 2009 7:47 pm


Bonjour,
sam. juil. 14, 2018 8:25 pmT-Tel a écrit :
Je me demande par exemple quelle est la preuve mathématique (si elle existe) derrière l'affirmation "Quelle que soit l’algorithme, s'il est exécuté en boucle, on retombera toujours sur la configuration originelle"
Ce n'est vrai que si on part d'un cube résolu. Sinon, c'est faux en général (enfin, si j'ai bien compris le sens de configuration originelle que je considère être un cube résolu). Quant à la preuve, elle est ultra-simple : on associe à un cube un groupe de permutations des pièces (celui engendré par les 6 mouvements possibles du cube). Or dans un groupe, si on élève n'importe quel élément à une puissance égale à l'ordre du groupe (le nombre d'éléments du groupe), on obtient l'élément neutre du groupe (conséquence directe du théorème de Lagrange pour les groupes finis).

Sinon, pour ce qui est de sites convenables, une recherche google m'en a très vite donné.
Par exemple : http://math.univ-lille1.fr/~bhowmik/ens ... _rubik.pdf
Mais je pense que rapidement, ça va être dur à lire si on n'a pas un niveau bien correct en mathématiques. Pas facile dans ce domaine de faire dans la vulgarisation, à vrai dire.
T-Tel


Salut,

Merci pour tes indications. Quand je parlais de configuration originelle, je parlais en fait de la configuration du cube avant qu'on ait commencé à agir dessus (pas nécessairement résolu donc).

Apres un peu de recherche de mon coté, j'ai constaté très vite que je pouvais comparer un cube à des choses que je connaissait un peu comme l'arithmétique modulaire ou encore les diagrammes d'état/expressions régulières.

Merci pour ton document également, je ne me suis pas encore penché dessus mais il a l'air très intéressant.

Je cherchait des sources avec une quantité raisonnable de vulgarisation en fait, quand j'ai cherché a faire l'analogie avec des chaines youtube comme Science4All ou Numberphile... Bah en fait je suis tombé sur des vidéos intéressantes (en anglais, certes).

Merci encore de ton aide en tout cas
fabien63
Bavard intarissable
Messages : 77
Enregistré le : ven. juil. 13, 2018 4:50 pm


bonjour

ok avec Philfully, juste que sa réponse est vraie quelque soit la configuration initiale du cube.
En élevant à une certaine puissance la combinaison de mouvements on tombera sur l’élément neutre du groupe des permutations (= l'identité). et donc on retombera sur la config de départ (qui peut être le cube résolue ou n'importe quelle autre configuration)


Pour la seconde question "Quel est le plus court algorithme permettant de passer par l’ensemble des configurations d'un rubik's Cube"". je ne sais pas si il existe, mais cet algorithme ne pourra être que théorique. car même si il existe, vu le nombre de configuration possible du cube 3x3x3 (environ 4,3252 x 10^19), il faudrait des années pour les passer toutes : à raison de 1000 combi par seconde il faut 1 370 573 278 années pour passer toutes les combinaisons.
Philfully
VIP au club des 1000
Messages : 2352
Enregistré le : mer. nov. 11, 2009 7:47 pm


mer. juil. 18, 2018 3:41 pmfabien63 a écrit :
ok avec Philfully, juste que sa réponse est vraie quelque soit la configuration initiale du cube.
J'avais en effet mal compris sa question. Je pensais qu'il croyait qu'on pouvait résoudre le cube en prenant n'importe quel algo et en le répétant le nombre de fois nécessaire. Désolé (surtout que c'est assez naïf de croire qu'une telle chose est possible... j'aurais pu comprendre de moi-même que ce n'était pas ce qu'il pensait...).
mer. juil. 18, 2018 3:41 pmfabien63 a écrit :
Pour la seconde question "Quel est le plus court algorithme permettant de passer par l’ensemble des configurations d'un rubik's Cube"". je ne sais pas si il existe, mais cet algorithme ne pourra être que théorique. car même si il existe, vu le nombre de configuration possible du cube 3x3x3 (environ 4,3252 x 10^19), il faudrait des années pour les passer toutes : à raison de 1000 combi par seconde il faut 1 370 573 278 années pour passer toutes les combinaisons.
Etant donné qu'il y a un nombre fini de configurations, il existe au moins un algorithme passant par toutes les configurations. Dès lors, l'ensemble des algorithmes passant par toutes les configurations n'est pas vide. Si on considère la fonction qui associe à chaque algorithme sa longueur, l'image par cette fonction de l'ensemble des algorithmes est une partie de N, l'ensemble des entiers naturels. De fait, cet ensemble n'est pas vide et donc admet un plus petit élément. La fonction étant surjective sur son image, il existe donc un algorithme optimal passant par toutes les configurations du cube.

Cependant, il doit être très long (comme tu le faisais remarquer) et je pense qu'on ne saurait actuellement pas calculer sa longueur tant le problème est complexe. On peut cependant en donner un ordre de grandeur. Puisqu'on sait que toute configuration du cube est atteignable en 20 mouvements maximum, on a donc un algorithme dont la taille va se trouver entre 4,3252 x 10^19 et ce nombre fois 20.
T-Tel


Bien sur il ne s'agirait pas de trouver cet algorithme mais d'en trouver la taille.
On peux aussi imaginer un algorithme beaucoup plus petit que le nombre de configuration qui, si on le répète, fera passer le cube par toutes ses configurations. Ce qui réduirait la taille de l'algorithme et permettrai de passer d'une taille comprise entre 4,3252 x 10^19 et ce nombre fois ~17 (la moyenne de taille d'algorithmes de résolution est ~17) à une taille comprise entre quelques dizaines et (4,3252x10^19) * 17

Ce qui est faisable (et que je vais essayer) c'est de trouver la taille de cet algorithme pour le cube 2*2*2 qui est raisonnablement parcourable, surtout en le réduisant à un diagramme d'état, qui, contrairement au cube 3x3x3 prends une taille raisonnable.
cyril
Helvète Underground
Messages : 3931
Enregistré le : jeu. juin 30, 2005 10:13 am


lun. juil. 23, 2018 2:26 pmT-Tel a écrit :

Ce qui est faisable (et que je vais essayer) c'est de trouver la taille de cet algorithme pour le cube 2*2*2 qui est raisonnablement parcourable, surtout en le réduisant à un diagramme d'état, qui, contrairement au cube 3x3x3 prends une taille raisonnable.
C'est faisable en effet, mais c'est chaud quand même :-D
https://www.speedsolving.com/forum/thre ... oup.34318/

... et le même auteur a ensuite trouvé la solution (hamiltonian circuit, qu'on appelle aussi Devil's Algorithm, par opposition au God's algorithm qui résout une position donnée en un minimum de mouvements) pour le 3x3x3 :
https://www.speedsolving.com/forum/thre ... ube.35505/

La beauté du truc, c'est que ces séquences parcourent une et une seule fois chaque position du cube : le diable (Devil) pourrait ainsi les appliquer pour résoudre n'importe quel mélange :snakeman:
7 messages Page 1 sur 1