mélange de Monge

Imaginez huit cartes empilées, numérotées de 1 en haut à 8 en bas. On prend les cartes une à une depuis le sommet. Après avoir posé la première, on place les suivantes tour à tour au-dessus puis au-dessous du nouveau paquet. Le geste ne laisse aucune place au hasard : un même ordre de départ produit toujours le même ordre d'arrivée. En répétant exactement l'opération, le paquet finit par retrouver son ordre initial.

Le mélange de Monge est une permutation déterministe des positions d'un paquet. La définition donnée ici porte sur un nombre pair de cartes. Si le paquet compte 2n cartes, le nombre n désigne donc la moitié de l'effectif. Les cartes sont numérotées de 1 à 2n, du sommet vers le dessous, avant l'opération.

Avec la convention de la définition, le nouvel ordre, lu lui aussi du sommet vers le dessous, est :

Autrement dit, les positions paires apparaissent d'abord en ordre décroissant, puis les positions impaires en ordre croissant. L'opération ne perd ni ne duplique aucune carte : elle réordonne un ensemble fini. Sa répétition revient donc nécessairement à l'identité après un nombre fini d'étapes. Si p désigne cette permutation, son ordre est le plus petit entier positif k pour lequel $p^k=\mathrm{i}\mathrm{d}p^k=\backslash mathrm\{id\}$. Cet entier dépend du nombre de cartes et de la convention choisie pour le geste.

On rencontre le mélange de Monge avec un paquet tenu en main, notamment dans un tour de cartes, mais aussi dans un exercice d'arithmétique ou de combinatoire. Quatre indices permettent de le reconnaître : les cartes partent une à une du sommet, un second paquet se forme, le placement alterne entre ses deux faces et la même règle peut être recommencée. Le support matérialise alors une permutation : l'information utile n'est pas la valeur des cartes, mais leur position avant et après chaque opération.

La grandeur recherchée est le plus petit nombre strictement positif d'opérations qui ramène toutes les cartes à leur position initiale. Premièrement, fixez la convention : numérotez le paquet du sommet vers le dessous et conservez ce sens de lecture. Deuxièmement, appliquez la règle aux positions, sans suivre seulement les valeurs visibles. Troisièmement, comparez la liste obtenue à la liste de départ après chaque opération. Quatrièmement, arrêtez-vous au premier retour complet.

Une carte isolée peut retrouver sa place avant les autres. L'œil peut alors croire le paquet reconstitué, mais le bon contrôle porte sur toutes les positions simultanément. Il faut aussi compter les opérations entières, et non les placements carte par carte.

Prenons 8 cartes. Les données sont les suivantes : l'ordre initial, lu du sommet vers le dessous, est 1, 2, 3, 4, 5, 6, 7, 8 ; une opération suit exactement la convention de la définition ; le résultat est relu dans le même sens.

1. Après une opération : 8, 6, 4, 2, 1, 3, 5, 7.
2. Après deux opérations : 7, 3, 2, 6, 8, 4, 1, 5.
3. Après trois opérations : 5, 4, 6, 3, 7, 2, 8, 1.
4. Après quatre opérations : 1, 2, 3, 4, 5, 6, 7, 8.

L'ordre initial n'apparaît dans aucune des trois premières listes et revient à la quatrième. Pour ce paquet et cette convention, l'ordre de la permutation vaut donc 4. Le contrôle est refaisable : appliquez encore une fois la règle à la quatrième liste ; vous retrouvez la première liste produite. Le schéma associé rend visible le premier réarrangement sans remplacer ce calcul.

En magie des cartes, l'opérateur choisit le mélange de Monge lorsqu'il veut une redistribution reproductible plutôt qu'un ordre imprévisible. Il doit garder le même sens du paquet et la même alternance à chaque passage.

Dans un exercice, on remplace le geste par une liste de positions. Cette représentation est préférable dès qu'il faut vérifier le retour du paquet, car chaque état intermédiaire devient contrôlable.

Pour tester un nombre de cartes donné, on répète la permutation jusqu'au premier retour complet. Suivre les cycles des positions devient plus efficace que recopier tout le paquet lorsque l'effectif augmente.

Le mélange de Monge ne doit pas être confondu avec un mélange aléatoire. Le critère est la reproductibilité : à ordre initial et convention identiques, Monge donne toujours la même permutation. Deux exécutions qui produisent volontairement des ordres imprévisibles relèvent d'un autre objectif, même si elles manipulent le même paquet.

La formule fournie concerne 2n cartes, donc un effectif pair. Pour un paquet impair, elle ne s'applique pas telle quelle : il faut d'abord définir sans ambiguïté quel côté reçoit la deuxième carte, puis recalculer la permutation obtenue.

Inverser le sens de lecture du paquet ou commencer l'alternance par l'autre face change l'ordre affiché. Le symptôme est immédiat : avec 8 cartes, la première liste n'est plus 8, 6, 4, 2, 1, 3, 5, 7. Il faut annoncer la convention avant de comparer deux calculs.

Des cartes portant la même valeur peuvent donner l'impression d'un retour précoce. Pour mesurer l'ordre de la permutation, chaque carte doit rester identifiable par sa position initiale, même si deux faces visibles se ressemblent.

L'arithmétique modulaire donne un langage pour étudier les retours périodiques de positions et relier les itérations d'une permutation à un calcul sur les restes.