Mélanges de cartes

Le problème suivant m'a été soumis par l'un de mes élèves (Anthony Tschirhard, INSA de Lyon, 51^e 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 incoercible, 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,…,2n-1,2n (n ∈ ℕ^* ) et superposés de bas en haut dans l'ordre croissant,

• le processus de mélange décrit ci-dessus conduit-il nécessairement au classement initial en un temps fini ?
• si oui, peut-on exprimer en fonction de n le nombre minimum de mélanges nécessaires pour retrouver le classement initial ?
• si les n premiers jetons sont verts et les n derniers rouges, peut-on arriver au regroupement initial des jetons (la pile du bas constituée de jetons verts, celle du haut de rouges) éventuellement dans le désordre quant à la numérotation ?

(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⁵, 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.

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 à ±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 ou . L'un des deux ensembles sera d'une utilisation plus commode que l'autre selon le cas étudié. Les permutations associées à 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 à ±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,… les permutations relatives à l'énumération 1,2,3,…,2n et celles associées à 0,1,2,…,2n-1. On passe par exemple de la permutation f à la permutation selon la relation pour tout .

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

• Dans la section II, nous présentons la modélisation du problème en introduisant toutes les permutations relatives aux différents mélanges de cartes. Certaines permutations redondantes ne seront pas nécessairement utiles, mais nous avons choisi de les écrire systématiquement afin de garder une homogénéité de notations ainsi qu'une logique de présentation. Selon les cas étudiés, certaines d'entre elles serviront à calculer la période du mélange en question, alors que d'autres permettront le calcul explicite des itérations successives.
• Dans la section III, nous formulons de manière implicite les réponses relatives au calcul de périodes des mélanges étudiés.
• Dans les sections IV et V, nous calculons explicitement, en faisant appel au calcul binaire, toutes les itérations successives de certaines permutations significatives, dans les cas particuliers où n est une puissance de 2 à ±1 près, ce qui permet de fournir une réponse explicite aux questions posées.
• Dans la section VI, nous examinons brièvement le cas d'un jeu contenant un nombre impair de cartes.
• Dans la section VII, nous décrivons un procédé simple pour déplacer une carte donnée vers une position prédéfinie dans le cas où n est une puissance de 2.
• Nous terminons dans la section VIII par une tentative de généralisation à un paquet de cartes divisible par un nombre supérieur à deux.