L'ordre ou le désordre ?

Prenons un jeu de trente-deux cartes non triées et disposons les cartes en un rectangle de quatre rangées de huit cartes. Ensuite, trions les cartes de chaque rangée dans un ordre décroissant de gauche à droite, l’ordre des cartes étant l’ordre habituel de valeur des cartes (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é. Eh bien, il n’en est rien : après ce second tri colonne par colonne, les rangées de la nouvelle configuration seront toujours triées, et ce, 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).

Chacun son tour

Un tour de « cartomagie » simple est basé sur ce principe. Séparons un jeu de trente-deux cartes en quatre paquets de huit cartes. Trions les cartes de chaque paquet en ordre croissant de leurs valeurs. Posons les quatre paquets faces contre table. Ensuite, prenons une carte de chaque paquet, trions ces quatre cartes, les plus forte étant dessus, puis disposons-les en colonne de haut en bas, toujours face contre table. Répétons cette opération de façon à 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 que les cartes 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). Dans cet algorithme, pour trier n données numérotées de 1 à n, on commence par trier toutes les données portant des numéros espacés de k (k < n), ce qui revient à disposer les données en rangées de k éléments puis à trier les colonnes. L’algorithme se continue en triant les données portant des numéros espacés de k – 1, puis de k – 2, k – 3…, ce qui revient à diminuer le nombre de colonnes (et 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 suivant : cœur > carreau > pique > trèfle.

1. Si l’on trie les rangées d’abord selon la valeur des cartes, et en cas d’égalité selon la couleur, qu’obtiendra-t-on après le tri des colonnes ?

2. Si l’on trie les rangées d’abord selon la couleur des cartes, et lorsque des cartes sont de la même couleur, selon leurs valeurs, qu’obtiendra-t-on après le tri des colonnes ?