Les tours de magie avec des cartes à jouer peuvent grossièrement se classer en deux grandes catégories.

• La première se base sur la dextérité du magicien. A force d’entraînement, ce dernier arrive à dissimuler ou faire apparaître habilement la carte de son choix.
• La deuxième catégorie repose sur les propriétés des mélanges et arrangements de cartes. Dans cet article, nous allons illustrer cette dernière à l’aide du mélange de Josèphe.

Josèphe devant Vespasien.

Cette façon de battre les cartes tire son nom d’une histoire bien peu réjouissante. Au premier siècle après Jésus-Christ, Flavius Josèphe (37-100) est piégé dans une grotte avec ses compagnons. Ceux-ci, refusant de se rendre aux Romains, organisèrent leur suicide collectif comme suit. Placés en cercle, Josèphe et ses compagnons suppriment une personne sur deux jusqu’au dernier. Celui-ci sera le seul membre du groupe à devoir se donner la mort. Dans pareille situation, se pose une question élémentaire de survie : en fonction de la taille initiale du groupe, quelle position doit occuper Josèphe s’il veut, pour échapper à son funeste sort, être l’ultime survivant. L’histoire raconte que seuls Josèphe et un compagnon réchappèrent de cette bien triste aventure. Voir par exemple les pages Wikipédia.

Il n’en faut pas plus pour que les mathématiciens Ronald Graham, Donald Knuth et Oren Patashnik présentent, dans un ouvrage paru en 1994, la fonction de Josèphe qui, pour un pour groupe de $n$ individus, fournit la position $J(n)$ de l’ultime survivant. On retrouve déjà une trace de ce problème mathématique dans un ouvrage datant de 1947 et écrit par Walter William Rouse Ball qui était lui-même magicien amateur. La figure ci-dessous illustre le problème de Josèphe pour un groupe de 6 compagnons et montre que $J(6)=5$. La croix noire représente le compagnon supprimé à l’étape en cours et les deux flèches permettent de compter un individu sur deux parmi les survivants (le compagnon compté en premier est épargné et désigné par un rond vert).

Où doit se placer Josèphe dans un groupe de 6 personnes ?

Revenons à notre tour de magie. Prenez un tas de huit cartes ordonnées et numérotées de 1 à 8.

Le tas de cartes (avant).

L’idée est, comme dans l’histoire de Josèphe, de supprimer une carte sur deux en épargnant la première.

A chaque étape, la taille du tas diminue et les cartes placées sur la table s’empilent pour former un nouveau tas. Les figures ci-dessous représentent la succession des déplacements effectués. Les cartes roses représentent le tas en main, les cartes vertes forment le tas constitué sur la table.

Les 3 premières étapes du mélange.

Les 5 dernières étapes du mélange.

Que remarque-t-on lorsque l’on compare le tas initial et le tas obtenu sur la table après les huit étapes ? L’as est toujours en première position (au sommet du tas). Par contre, le 5 occupe à présent la deuxième position, le 2 est quant à lui relégué à la huitième position, etc. Autrement dit, les huit cartes du tas ont été permutées.

Permuter $n$ éléments distincts revient à fixer la manière de les ordonner.

Contrairement à un battage aléatoire, la permutation effectuée ici n’est pas quelconque.

Le tas de cartes (après).

On représente les déplacements effectués, i.e., la permutation, à l’aide de la notation suivante où chaque colonne montre la valeur d’une carte avant et après battage :
\[ \left(\begin{array}{cccccccc} 1&2&3&4&5&6&7&8\cr 1&5&7&3&8&6&4&2\cr \end{array}\right). \]
On observe tout d’abord que les cartes 1 et 6 ne bougent pas. Ensuite, là où l’on trouvait un 2, on y trouve à présent un 5 et ainsi de suite. Remarquez que les cartes 2, 5 et 8 échangent leur position, tout comme celles aux positions 3, 7 et 4. On est en présence de deux permutations circulaires. Pour avoir d’autres illustrations des permutations, voir l’article Permutations jonglistiques (ou encore ceux repris en notes [1]).

Les cycles apparaissant dans le mélange de Josèphe.

Pour étudier le battage de Josèphe avec un tas de 8 cartes, il suffit de mettre en évidence les deux permutations circulaires qui le composent.

Il s’agit là de l’illustration d’un phénomène tout à fait général dans l’étude des permutations. Reprenons le tas obtenu et battons-le à nouveau à l’aide du mélange de Josèphe. Si vous réalisez l’opération, vous devriez obtenir le tas représenté ci-dessous.

Après un second mélange.

En particulier, les cartes en position 1 et 6 n’ont toujours pas bougé [2]. Par contre, le tas de cartes obtenu semble battu de façon aléatoire. C’est maintenant que la magie intervient et surtout un peu de boniment ! Après avoir saupoudré un peu de poudre de perlimpinpin sur le tas et après avoir, bien évidemment, fait souffler le surplus de poudre par un spectateur, le magicien bat une troisième fois le jeu à l’aide du mélange de Josèphe. Miracle... le jeu est à nouveau ordonné ! Ceci n’a bien sûr rien de surprenant, l’analyse développée ci-dessus met en évidence deux cycles de 3 cartes : à chaque battage, les cartes 2, 5, 8 échangeant tour à tour leur position, 3 battages sont ainsi nécessaires pour que les cartes retrouvent leur position initiale et il en va de même des cartes 3, 7 et 4 (la figure ci-dessous met en évidence un des deux cycles lors des deux premiers battages). Avec un peu de mise en scène, le tour fonctionne très bien.

Les échanges de cartes des deux premiers battages.

Pourquoi 8 cartes et pas 9 ou 10 ? On peut bien sûr essayer, mais dans ce cas, le tour risque de devenir bien long. En effet, voici tout d’abord la permutation obtenue avec 9 cartes
\[ \left(\begin{array}{ccccccccc} 1&2&3&4&5&6&7&8&9\cr 5&9&1&8&4&7&2&6&3\cr \end{array}\right). \]
On y observe un unique cycle de longueur 9 : on passe, dans l’ordre, par les positions 1, 5, 4, 8, 6, 7, 2, 9, 3 avant de revenir en 1. Il faudra donc que le magicien batte le jeu à 9 reprises pour qu’il soit à nouveau ordonné. Difficile dans ces conditions de garder les spectateurs en haleine. Maintenant pour 10 cartes, le mélange de Josèphe fournit la permutation
\[ \left(\begin{array}{cccccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10\cr 3 & 10& 5 & 9 & 1 & 8 & 4 & 7 & 2 & 6 \cr \end{array}\right) \]
avec un cycle pour les 3 cartes 1, 3 et 5 et un second cycle formé des 7 cartes restantes. Il sera donc nécessaire de battre le jeu 21 fois pour revenir à la configuration initiale !

Un autre tour. Un spectateur bat $n$ cartes (le mieux est de laisser au spectateur le soin de fixer lui-même le nombre $n$ de cartes). Le magicien inspecte le tas battu et prédit une carte (ou bien, note sa prédiction qui ne sera révélée qu’à la fin du tour). Le magicien bat à présent le jeu, à la façon de Josèphe, jusqu’à ce qu’il ne reste qu’une seule carte en main. Bien évidemment, la carte restante est celle de la prédiction... Il s’agit simplement pour le magicien de bien connaître la fonction de Josèphe $J(n)$ introduite en début d’article et de savoir la calculer rapidement (ou de connaître à l’avance sa valeur pour la taille du tas choisi au départ). Lorsqu’il inspecte le jeu, le prestidigitateur compte les cartes et repère directement quelle carte sera l’ultime survivante. Avec 8 cartes, nous avons vu que la carte qui restera en dernier est en fait la première du tas, autrement dit $J(8)=1$. En fonction de la taille $n$ du tas de départ, le tableau suivant reprend la position $J(n)$ de la carte restante que doit connaître le magicien
\[ \begin{array}{c|cccccccccccccc} n&2&3&4&5&6&7&8&9& 10& 11& 12& 13& 14& 15\cr \hline J(n)&1&3&1&3&5&7&1&3&5& 7& 9& 11& 13& 15\cr \end{array} \]

\[ \begin{array}{c|ccccccccccccccc} n&16&17&18&19&20&21&22&23&24&25&26&27&28&29&30&31\cr \hline J(n)&1& 3& 5& 7& 9& 11& 13& 15& 17& 19& 21& 23& 25& 27& 29& 31\cr \end{array} \]
Graham, Knuth et Patashnik mènent plus loin l’analyse de cette fonction de Josèphe et ne se bornent pas à en dresser le tableau des premières valeurs. Ils observent qu’éliminer une carte sur deux permet de calculer la valeur de $J(2m)$ ou $J(2m+1)$ à partir de celle de $J(m)$. Vous me direz que le magicien doit être un as du calcul mental pour trouver immédiatement la valeur de la fonction de Josèphe. En fait, il y a encore un truc ! Si on connaît l’écriture [3] en base 2 de $m$, disons de la forme ${\color{blue}1}\boxed{a_t\cdots a_0}$, on peut montrer que l’écriture en base 2 de $J(m)$ est donnée $\boxed{a_t\cdots a_0} {\color{blue}1}$.