Mars 2015, 2ème défi
le 13 mars 2015 à 12:44, par Idéophage
Considérons les cubes en s’autorisant les doublons. Il y a 6 faces par cubes et 2 possibilité de diagonale par face, soit 2^6 cubes.
Considérons le graphe dont chaque nœud est un cube et chaque arête représente une rotation pour passer du premier cube au deuxième. Il peut y avoir plusieurs arêtes entre un couple de nœuds. On voit que nos cubes vont être partitionnés en ilots connexes. Chaque ilot est symétrique en tous ses nœuds (il s’agit du même cube tourné dans tous les sens). On aimerait compter le nombre d’ilots (il s’agit du nombre de cubes vraiment différents).
Comme on aimerait compter 1 pour chaque ilot, on va regarder pour chaque nœud combien il y a d’autres nœuds que l’on peut atteindre à partir de lui. Chaque nœud d’un ilot de taille n va compter comme 1/n ilot. On voudrait donc ajouter, pour chaque cube, 1/(nombre d’autres cubes que l’on peut atteindre). La structure étant très symétrique, il suffit de savoir combien de rotations on a qui font que l’on retourne sur le même cube pour savoir combien d’autres cubes on peut atteindre. En effet, comme tout est symétrique, il y a toujours le même nombre d’arêtes pour passer d’un nœud à l’autre dans un ilot donné. Du coup, comme on connait le nombre de rotations possibles, on peut diviser le nombre total de rotations par le nombre de rotations « qui ne font rien » pour avoir le nombre de nœuds dans l’ilot. Si l’on note neutre(c) le nombre de rotations qui transforment le cube c en lui-même, si l’on note M le nombre total de rotations, chaque cube va donc compter comme neutre(c)/M. En fait, cela revient à prendre le graphe, compter le nombre de flèches qui partent d’un nœud et retournent sur lui-même, et diviser par le nombre de rotations. Pour compter cela, on peut procéder nœud par nœud, mais c’est plus facile de procéder rotation par rotation : pour chaque rotation, on compte combien de cubes elle transforme en lui-même.
Il s’agit du lemme de Burnside.
Il y a 24 rotations possibles dans un cube :
* l’identité : elle laisse fixe tous les cubes, soit 2^6.
* 6 rotations de pi/2 ou -pi/2, d’axe passant par le centre de deux faces opposées : aucun cube n’est laissé fixe (on retourne forcément les diagonales des faces de l’axe).
* 3 rotations de pi de même axe que précédemment : le choix de 4 faces fixe toutes les autres (on a deux faces envoyées sur elles-mêmes et les autres groupées par paires).
* 6 rotations de pi, d’axe passant par le milieu de deux côtés opposés : on doit fixer 3 faces puisqu’elles sont toutes groupées par paires.
* 8 rotations d’angle 2pi/3 ou -2pi/3, d’axe passant par deux sommets opposés : on doit fixer 2 faces puisqu’elles sont toutes groupées par 3.
Ainsi, dans le graphe, on a 1*2^6 + 6*0 + 3*2^4 + 6*2^3 + 8*2^2 = 192 arcs qui retournent sur leur nœud de départ. On divise par 24 et on obtient qu’il y a 8 cubes vraiment différents.
En remarquant que 8 = 2^3, on peut essayer de voir si on ne peut pas faire une preuve sans passer par la théorie des groupes. Peut-être que chaque cube est identifié par 3 paramètres binaires... J’avais pensé à identifier les cubes par si les faces opposées sont ou non dans le même sens mais il y a deux possibilités pour toutes les faces opposées dans le même sens.
Répondre à ce message