L'ordre ou le désordre ?

Plusieurs tours de cartes sont basés sur une propriété connue sous le nom de non-messing-up theorem. En d’autres termes, un « théorème du non-dérangement ».

Prenons un jeu de trente-deux cartes non triées et disposons les cartes en un rectangle de quatre rangées de huit cartes. Trions les cartes de chaque rangée dans un ordre décroissant de gauche à droite, selon l’ordre habituel des valeurs : as, roi, dame, valet, dix, neuf, huit, sept. Lorsque deux cartes ont la même valeur, on les place côte à côte de façon quelconque.

Dans chacune des huit colonnes, les cartes ne sont a priori pas triées. Trions-les donc dans chaque colonne, dans un ordre décroissant de haut en bas du rectangle.

On pourrait penser qu’après ce second tri, celui des rangées devrait être perturbé. Il n’en est rien : après ce tri colonne par colonne, les rangées de la nouvelle configuration sont toujours triées, quelle que soit la configuration de départ.

Cette propriété est connue depuis longtemps, mais elle n’a été expliquée qu’il y a une soixantaine d’années. En 1971, les mathématiciens américains David Gale (1921–2008) et Richard Manning Karp (né en 1935) la démontrent dans une publication du Centre de recherche opérationnelle de l’université de Californie à Berkeley.

Un tour de « cartomagie » simple est basé sur ce principe. Séparons un jeu de trente-deux cartes en quatre paquets de huit cartes et trions les cartes de chaque paquet dans l’ordre croissant de leurs valeurs. Posons les quatre paquets faces contre table.

Prenons ensuite une carte de chaque paquet, trions ces quatre cartes en plaçant la plus forte dessus, puis disposons-les en colonne de haut en bas, toujours face contre table. Répétons cette opération afin de disposer toutes les cartes en un rectangle de huit colonnes et quatre rangées. Retournons alors toutes les cartes et faisons observer à notre public ébaubi qu’elles se sont triées d’elles-mêmes !

L’idée de cette méthode apparaît dans un algorithme de tri appelé tri de Shell, inventé en 1959 par le mathématicien américain Donald Lewis Shell (1924–2015). Pour trier $nn$ données numérotées de $11$ à $nn$, on commence par trier toutes les données portant des numéros espacés de $kk$, avec , ce qui revient à disposer les données en rangées de $kk$ éléments puis à trier les colonnes. L’algorithme continue en triant les données portant des numéros espacés de $k\text{–}1k\; –\; 1$, puis de $k\text{–}2k\; –\; 2$, $k\text{–}3k\; –\; 3$…, ce qui revient à diminuer le nombre de colonnes, ainsi que leur longueur, et à trier ces colonnes.

Si l’on souhaite un tri plus précis des cartes, on peut ajouter la règle suivante : lorsque deux cartes sont de même valeur, on considère l’ordre cœur > carreau > pique > trèfle.