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 :/
Problèmes mathématiques autour des cubes
- Philfully
- VIP au club des 1000
- Messages : 2358
- Enregistré le : mer. nov. 11, 2009 7:47 pm
- Localisation : Belfort
- Contact :
Re: Problèmes mathématiques autour des cubes
Bonjour,
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.
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.
Philfully
Re: Problèmes mathématiques autour des cubes
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
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
Re: Problèmes mathématiques autour des cubes
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.
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 : 2358
- Enregistré le : mer. nov. 11, 2009 7:47 pm
- Localisation : Belfort
- Contact :
Re: Problèmes mathématiques autour des cubes
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...).
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.fabien63 a écrit : ↑mer. juil. 18, 2018 3:41 pm 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.
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.
Philfully
Re: Problèmes mathématiques autour des cubes
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.
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 : 4097
- Enregistré le : jeu. juin 30, 2005 10:13 am
- Localisation : En Suisse
- Contact :
Re: Problèmes mathématiques autour des cubes
C'est faisable en effet, mais c'est chaud quand mêmeT-Tel a écrit : ↑lun. juil. 23, 2018 2:26 pm
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.
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
Solution pour les débutants, sur francocube !