Mouvements du Rubik's cube

[invite425270e0]

Plop,

Voilà je fais mon sujet de tipe et je suis confronté à un problème. Dans mes recherches je trouve que le nombre de positions qui sont "atteignables" par les mouvements basiques ( trois par face donc 18), suit la formule de récurrence suivante: S_n=12*S_n-1-18*S_n-2 (avec n le nombre de mouvements)
On peut expliciter cette suite en fonction de n en utilisant le polynôme caractéristique etc...
Puis, on peut calculer que le cube peut avoir N = 11*7²*5³*3¹⁴*2²⁷ positions différentes. Je cherche donc le plus petit n tel que S(n) > N et je trouve 20. En continuant mes recherches, je vois qu'on ne sait pas si on peut atteindre toutes les positions en ce nombre minimum de mouvements, et de plus que certaines positions nécéssitent 23 mouvements...
Avez-vous des explications? Mon raisonnement me semble pourtant pas faux (c'est pour ça que je demande votre aide^^)

Cordialement, Universmaster.
-----

[invitebe0cd90e]

A vue de nez, je dirais que c'est parce que dans les mouvements que tu comptes avec ta recurrence, tu retombes certainement plusieurs fois sur la meme position. Exemple tout bete : il y a des mouvements qui commutent, par exemple l'operation "tourner une face d'un quart de tour", appliqué a 2 faces opposées, t'amenent dans la meme configuration quel que soit l'ordre dans lequel tu les appliques.

Donc comparer brutalement les cardinaux n'est pas pertinent, je pense.

Au passage, je ne comprends pas quand tu dis qu'il y a 3 mouvements elementaires par face, pour moi il y en a 2 : tourner d'un quart de tour dans le sens des aiguilles d'une montre, et tourner d'un quart de tour en sens inverse. Comme en plus ces mouvements sont inverse l'un de l'autre, d'un point de vue theorie des groupes, le groupe du Rubik's est engendré par 8 éléments correspondant aux 8 faces.

D'une maniere generale, il est tres difficile de borner superieurement la longueur des mots en les générateurs necessaires pour representer les éléments du groupe.

[invite425270e0]

Re,

Il y a 3 mouvements si on considère par face: un quart de tour sens direct, deux quart deux tours sens direct, trois quart de tours sens direct. Avec la formule de récurrence, justement, on enlève ces positions répétés, sinon il y en aurait (6*3)^n . Donc normalement on devrait pouvoir comparer les cardinaux non?

Cordialement

[invitebe0cd90e]

Re,

Il y a 3 mouvements si on considère par face: un quart de tour sens direct, deux quart deux tours sens direct, trois quart de tours sens direct. Avec la formule de récurrence, justement, on enlève ces positions répétés, sinon il y en aurait (6*3)^n . Donc normalement on devrait pouvoir comparer les cardinaux non?

Cordialement

j'avais compris que c'est ces mouvements que tu considerais, mais c'est un peu redondant a vue d'oeil, non ?

Es tu vraiment sur d'enlever toutes les positions répétées ? A priori il se peut que des sequences differentes n'aboutissent à la meme position qu'au bout d'un nombre elevé de mouvements, et ta formule a l'air trop simple (a l'air de ne pas avoir assez de "memoire") pour en tenir compte, en meme temps je n'ai pas regardé en detail.

[A voir en vidéo sur Futura]