David Madore's WebLog: Encore un taquin de Mathieu

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #1640 [older|newer] / Entrée #1640 [précédente|suivante]:

(vendredi)

Encore un taquin de Mathieu

J'avais déjà proposé (deux fois) des petits jeux comme ça : celui qui se trouve en bas de cette entrée (cliquez ici s'il n'apparaît pas bien ci-dessous, et maudissez avec moi la norme HTML qui ne permet pas d'inclure un document dans un autre en l'insérant à sa taille naturelle) est donc ma troisième tentative, et j'en suis un peu plus content parce que, contrairement aux deux précédents qui étaient sérieusement trop durs, je crois qu'il est vraiment jouable (et construit de façon un peu moins ad hoc). Par contre, je ne suis pas du tout content de l'interface, comme je vais l'expliquer.

Le but du jeu, donc, est de mélanger les nombres de 1 à 24 puis d'arriver à les remettre dans l'ordre évident dans lequel ils sont présentés initialement. La commande ¿ (un point d'interrogation à l'envers, ne me demandez pas pourquoi) mélange complètement le taquin, et la commande (une croix) le réinitialise à sa position de départ ; quant à ¡ (un point d'exclamation à l'envers), elle effectue un mélange partiel, que j'appelle un m12lange pour une raison que je vais expliquer, qui n'échange pas de nombres entre les deux moitiés (dodécades), et qui peut donc servir de puzzle plus simple pour s'entraîner avant de passer au problème complet. Bref, votre mission est de mélanger — ou au moins de m12langer — le puzzle, puis d'arriver à le remettre dans son état initial en n'utilisant que les commandes de mouvement que je vais expliquer (mais peut-être que le mieux est d'expérimenter avec plutôt que de lire les instructions). Avant que quelqu'un n'exprime sa déception à ce sujet : non, il n'y a pas de message de félicitation quand on arrive à remettre le puzzle en ordre.

Expliquons donc quels sont les mouvements autorisés. Tout d'abord, les nombres sont placés en deux tableaux de 3 lignes × 4 colonnes (qu'on pourrait appeler dodécades), le tableau d'en haut contenant initialement les nombres de 1 à 12 et celui d'en bas de 13 à 24. Parmi les mouvements possibles, on peut faire n'importe quelle permutation des trois lignes d'un tableau, à condition de faire la même sur l'autre tableau : pour concrétiser ça, j'ai mis des commandes et , qui permutent cycliquement les trois lignes de chaque tableau, et qui échange les deux lignes d'en bas de chaque tableau : avec ça, on arrive assez facilement à faire n'importe quelle permutation des lignes (la même sur les deux tableaux). Pour ce qui est des colonnes, on à le droit à ce qu'on appelle une permutation paire (toujours la même sur les deux tableaux) : concrètement, j'autorise à faire une permutation cyclique des trois colonnes de gauche, ou des trois colonnes de droite, avec les commandes et situées de part et d'autre du losange central — celles à gauche permutent cycliquement les trois colonnes de gauche et celles à droite les trois colonnes de droite. Ensuite, on a l'opération la plus importante, le flip de Mathieu, commandée par le losange  : elle échange huit paires de nombres (quatre en haut et quatre en bas, mais pas organisées de la même façon), rappelées par des couleurs sur les cases en question — le contenu de chaque case coloriée est échangé avec celui de la case de même couleur. (Chaque paire est composée de deux cases adjacentes en diagonale — du moins, pour le tableau du bas, si on regarde les colonnes cycliquement.)

Aucune des opérations qu'on vient de décrire n'échange des nombres entre les deux tableaux : les nombres qui étaient en haut restent en haut et ceux d'en bas restent en bas ; je dirai que tout mélange effectué avec les différentes opérations que je viens de décrire est un m12lange du tableau : mais pour avoir un mélange complet, il me faut une dernière opération. Celle-ci est représentée par (flèche haut-bas avec une base horizontale), et elle échange deux des trois lignes du tableau supérieur (les deux lignes d'en bas, en l'occurrence) avec les deux mêmes lignes du tableau inférieur (en combinant avec des permutations cycliques, on voit bien sûr qu'on peut facilement faire échanger n'importe quel nombre pair de lignes entre les deux tableaux).

Ces règles étant décrites, que peut-on en dire mathématiquement ? Il y a 244823040 façons de mélanger le puzzle, c'est-à-dire seulement la fraction 1/2534272925184000 des 620448401733239439360000 manières en tout dont on peut permuter 24 objets. Néanmoins, ces 244823040 permutations, qui forment le groupe M24 de Mathieu, suffisent à permettre de placer cinq nombres quelconques (parmi les 24) à cinq emplacements quelconques : on dit qu'il est cinq fois transitif — et c'est assez remarquable, parce que tout puzzle consistant en des permutations, arbitrairement composables, sur n objets et qui permettrait d'en placer six quelconques à six emplacement quelconques (i.e., qui serait six fois transitif), ou a fortiori plus que six, réaliserait obligatoirement[#] toutes les permutations de ces n objets, sauf peut-être à un échange près (autrement dit, les permutations paires : tout le monde sait sans doute que le taquin habituel ne permet de réaliser que la moitié des permutations imaginables). En particulier, si on ajoutait n'importe quelle nouvelle opération (qui ne soit pas déjà réalisable avec celles proposées), on pourrait obtenir n'importe quel arrangement des 24 nombres ou au moins tous les arrangements pairs.

Quant aux façons de m12langer le puzzle, il en existe 95040 (là, ce n'est vraiment pas énorme !), c'est-à-dire 1/5040 des 479001600 manières de permuter 12 objets, et, de nouveau, le groupe des permutations ainsi formées, qui est le groupe M12 de Mathieu, opère cinq fois transitivement, c'est-à-dire que sans échanger de nombres entre les deux tableaux on peut arriver à placer cinq quelconques d'un tableau donné à un emplacement quelconque dans ce tableau. Donc ce puzzle, contrairement aux précédentes tentatives que j'avais faites pour présenter le groupe M24 sous forme de jeu de taquin, montre clairement comment le sous-groupe M12 apparaît, et permet de s'en servir comme d'un mini-puzzle à l'intérieur du puzzle complet, si on s'interdit simplement d'utiliser l'opération qui échange des lignes entre les deux tableaux (et si on m12lange avec ¡). Ce mini-puzzle, d'ailleurs, est tout à fait jouable tout en étant loin d'être évident ! Et puis, il y a quelque chose d'un peu magique, quand on arrive à remettre en ordre le tableau du haut après l'avoir m12langé, à constater que celui du bas se remet aussi magiquement[#2] dans l'ordre.

Mes opérations ne sont pas tout à fait irredondantes : par exemple, il n'est pas nécessaire de disposer d'une opération échangeant les deux lignes inférieures (de chaque tableau), et il n'est pas non plus nécessaire de pouvoir faire une rotation cyclique des trois colonnes de droite — on peut engendrer tout M12 avec juste une rotation cyclique des lignes, une rotation cyclique des trois colonnes de gauche, et le flip, et M24 avec l'opération en plus. (Mais ça me semblait tout de même pertinent de tout autoriser, pour que le puzzle ne soit pas injouable, et aussi parce que ça me semble plus logique avec toutes les opérations. Si on est téméraire, on peut cependant essayer de jouer avec seulement les opération que je viens de dire.) En revanche, le flip est évidemment indispensable : sans lui, deux nombres situés sur la même ligne ou colonne resteront toujours sur la même ligne ou colonne, et on n'obtient que 288 permutations en tout.

J'ai expliqué que M24 ne contient qu'une toute petite fraction des 24!≈6×1023 permutations possibles de 24 objets : les joueurs de Rubik's cube auront peut-être tendance à rigoler de la taille de ce groupe, qu'est-ce que 245 millions d'éléments par rapport aux 4×1019 configurations du cube 3×3×3 ? Pourtant, je pense que c'est justement le fait que le groupe de Mathieu soit petit (donc très contraint) dans le groupe symétrique qui fait que le puzzle n'est pas très facile : on ne peut pas espérer trouver de façon d'échanger juste deux nombres, ou juste deux paires, ou quelque chose comme ça — le plus grand nombre d'éléments qu'on peut simultanément laisser fixe par une opération quelconque est huit (ou, si vous préférez, si neuf nombres quelconques sont à leur bonne place, le puzzle est forcément résolu ; et dans M12 c'est même cinq). En même temps, le fait que M24 soit quand même cinq fois transitifs signifie que le problème a énormément de symétries, on ne peut pas toutes les « voir » à la fois. Par rapport à mes présentations précédentes de M24 comme puzzle (ici et ), on a peine à croire que c'est le même groupe (à conjugaison près dans 𝔖24, c'est-à-dire à réétiquetage près), mais avec des générateurs différents : je pense que ce nouveau puzzle est à la fois plus simple à résoudre (je n'y arrive pas non plus sans aide de l'ordinateur, mais je n'y ai pas passé un temps fou, et j'arrive au moins à faire le mini-puzzle de M12) et moins artificiel (les mouvements proposés ne sont pas atrocement compliqués, et notamment j'arriverais à retenir toutes les règle, notamment les cases échangées par le flip de Mathieu, alors que dans mes précédentes descriptions c'était vraiment sorti d'un chapeau. Là, je crois que je vais retenir cette description des groupes de Mathieu.

Par contre, je ne suis vraiment pas content de mon interface en HTML+JavaScript : c'est atrocement peu maniable, et fort peu intuitif. Donc si quelqu'un trouve une autre façon de faire ça, une interface montrant facilement qu'on peut faire une permutation quelconque des lignes, une permutation paire des colonnes, l'échange d'un nombre pair de lignes entre les deux tableaux, plus le flip magique, ça m'intéresse. (Enfin, ça m'intéresse surtout si quelqu'un réalise cette interface, parce que donner des conseils c'est toujours facile…)

Trêve de blabla, voici le puzzle : jouez-y, c'est addictif !

[#] Techniquement : tout groupe de permutations sur n objets qui est six fois transitif est égal au groupe symétrique 𝔖n ou au groupe alterné 𝔄n ; et à part eux, les seuls qui soient cinq fois transitifs sont les groupes M12 et M24 de Mathieu, opérant naturellement sur 12 ou 24 objets. (J'en avais déjà parlé.) On peut aussi donner des listes de groupes opérant fidèlement de façon deux à quatre fois transitive, mais il y en a plus que ça.

[#2] En fait, si on fait correspondre le tableau du haut avec le tableau du bas dans lequel on a permuté cycliquement les colonnes d'un cran (dans un sens quelconque), on obtient une application qui associe à chaque élément de M12 un autre élément de ce même groupe, et qui préserve la composition : il se trouve que cette correspondance constitue l'unique (à conjugaison près) automorphisme extérieur de M12. Quant à M24, lui, il ne possède pas d'automorphisme extérieur : c'est un groupe complet.

↑Entry #1640 [older|newer] / ↑Entrée #1640 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées