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 là), 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.