À l'aide de votre mathématico-coach, plus jamais de pannes sèches !

Sommaire :

Mélanges de jetons

Exposition du problème

Le problème suivant m'a été soumis par l'un de mes élèves (Anthony Tschirhard, INSA de Lyon, 51ième promotion, grand rhétoricien à la verve désopilante) qui a une grande pratique de la magie. Lors d'une représentation sybaritique dans quelque cloaque non fréquentable, il se livre a quelques frasques regrettables : disposant d'une pile de \(2n\) jetons dont les \(n\) du bas sont verts et les \(n\) du haut sont rouges, il divise la pile en deux parties : l'une contenant les \(n\) jetons verts, l'autre contenant les \(n\) jetons rouges. Avec une dextérité indicible, de sa seule main droite il prend simultanément les deux piles de jetons, puis, dans un élan frénétique et incœrcible, procède à un mélange de ces deux dernières pour former une unique pile (de \(2n\) jetons) alternant parfaitement jeton rouge et jeton vert. Cette nouvelle pile est divisée à son tour exactement en son milieu donnant deux tas de \(n\) jetons et notre démiurge procède à un nouveau mélange intercalant alternativement un jeton de chaque tas pour former une nouvelle pile de \(2n\) jetons qu'il recoupe de nouveau en deux piles de \(n\) jetons et ainsi de suite.

Après plusieurs expériences (pour \(n < 8\)), notre thaumaturge s'aperçut qu'il retombait au bout d'un certain nombre de tels mélanges sur la pile initiale : les \(n\) jetons du bas sont verts et les \(n\) du haut sont rouges. Plus frappant encore, en numérotant et ordonnant les jetons, il semblerait que la première fois que l'on retrouve une pile de \(n\) jetons verts consécutifs et de \(n\) rouges de bas en haut, les jetons soient en fait exactement dans l'ordre initial.

Les questions cornéliennes qu'il m'a soumises étaient alors les suivantes : étant donnée une pile de \(2n\) jetons numérotés \(1,2,\dots,2n-1,2n\) (\(n \in\mathbb{N}^*\)) et superposés de bas en haut dans l'ordre croissant,

La solution

(Ce qui suit est un résumé. L'article complet est disponible au format PDF : Quelques mélanges parfaits de cartes).

Quelques mélanges parfaits de cartes

Il s'agit d'un problème classique bien connu du monde de la magie des cartes, la manipulation précédente étant souvent faite avec des cartes à jouer.

Le jeu habituel de \(32\) cartes est privilégié car le nombre \(32\) se décompose en \(2^5\), ce qui conduit à des propriétés remarquables. Dans la littérature, ce type de problème est abordé sous le vocable anglophone de « chip-shuffle » pour les jetons, de « riffle-shuffle » pour les cartes et plus précisément de « in-shuffle » et de « out-shuffle » selon le placement des cartes initiales de chaque paquet lors d'un mélange. Il a été considéré entre autres par le célèbre informaticien et magicien Elmsley en 1957. On trouvera également une large description historique du problème dans la section intitulée « some history of perfect shuffle ».

Les in-shuffles et out-shuffles sont des mélanges très proches.
Disposant d'un jeu de cartes que l'on coupe au milieu donnant deux paquets de cartes (un premier et un deuxième), l'in-shuffle du jeu initial consiste à démarrer le processus en plaçant la première carte du bas du premier paquet sur la première carte du bas du deuxième paquet. À l'opposé, l'out-shuffle consiste à démarrer en plaçant la première carte du bas du premier paquet sous la première carte du bas du deuxième paquet. Notons que dans le cas de l'out-shuffle, les première et dernière cartes restent immobiles tout au long de l'expérience.
On pourra consulter les sites internet Wikipedia et Mathworld pour un recensement de ces divers mélanges ainsi que d'autres.

Mélanges de jetons à travers le temps
Elmsley se posait la question plus complexe : est-il possible de déplacer la carte du dessus du paquet à une position donnée à l'avance à l'aide d'une succession de mélanges de nature in-shuffle ou out-shuffle ? La réponse est positive et il obtint un procédé pour accomplir une telle manipulation. Inversement, est-il possible de faire apparaître une carte donnée dans le jeu sur le haut du paquet de cartes, voire à une place quelconque selon un précédé similaire ? Récemment, les mathématiciens Diaconis et Graham (le premier auteur est également magicien) ont répondu positivement à la question générale du déplacement d'une carte donnée vers une position donnée. Ils ont proposé un algorithme indiquant le chemin à suivre (succession de in- et out-shuffles).

Reprenons les questions posées par mon élève.
La réponse à la première question est affirmative et la raison en est très simple.
Sommairement, on travaille dans un groupe fini de permutations, on revient donc à la position initiale au bout d'un nombre fini d'expériences, il s'agit d'un processus périodique.

La réponse à la deuxième question est également affirmative ; c'est un calcul de période et une formule implicite est disponible, voir e.g.les livres de Conway & Guy, de Herstein & Kaplansky, ou d'Uspensky & Heaslet. Néanmoins, une formule explicite ne semble pas accessible excepté pour les cas particuliers où \(n\) est une puissance de \(2\) à \(\pm 1\) près.
La troisième question semble rester à ma connaissance ouverte.

Dans cet article, je détaille le processus de l'in-shuffle – celui de l'out-shuffle s'en déduisant aisément – à l'aide de permutations de l'ensemble \(\{0,1,2,\dots,2n-1\}\) ou \(\{1,2,3,\dots,2n\}\). L'un des deux ensembles sera d'une utilisation plus commode que l'autre selon le cas étudié. Les permutations associées à \(\{0,1,2,\dots,2n-1\}\) sont particulièrement bien adaptées au calcul explicite des itérations successives (correspondant à la succession de mélanges parfaits) par le truchement des écritures binaires.

Aussi, je détaille toutes les permutations relatives aux deux numérotations en signalant laquelle permet de formuler le plus simplement possible la période recherchée. Je porte un intérêt particulier aux cas spécifiques mentionnés plus haut, à savoir lorsque \(n\) est une puissance de \(2\) à \(\pm 1\) près.
J'examine également d'autres exemples de mélanges parfaits : les mélanges de Monge qui sont des in/out-shuffles déformés par une symétrie.
Toute cette analyse permet d'accéder au calcul des périodes de chacun des mélanges décrits ici.

Par souci d'homogénéité des notations, on notera \(f,g,h,\dots\) les permutations relatives à l'énumération \(1,2,3,\dots,2n\) et \(\varphi,\psi,\chi,\dots\) celles associées à \(0,1,2,\dots,2n-1\). On passe par exemple de la permutation \(f\) à la permutation \(\varphi\) selon la relation \(\varphi(i)=f(i+1)-1\) pour tout \(i\in\{0,1,2,\dots,2n-1\}\).

Il est remarquable de constater que, bien au-delà de son aspect ludique, ce problème suscite des questions de nature algébrique avancées (théorie des groupes). L'étude approfondie de certaines permutations mises en jeu a été entreprise indépendamment de ce contexte par Lévy.
Ce problème connaît également des applications notamment en informatique (calcul parallèle, réseaux). Mentionnons enfin
l'existence d'autres types de mélanges d'une importance notoire qui ont retenu l'attention des mathématiciens : les mélanges aléatoires.

Plan de l'article