Mélange parfait
(brassage, battage d'un jeu de cartes)

Initialement on a la suite 1, 2, 3, 4 ... des entiers naturels non nuls.
On peut imaginer que ces nombres représentent les cartes d'un jeu, (ayant un nombre infini de cartes), numérotées à partir du sommet du paquet.

Les cartes du jeu sont progressivement mélangées par des battages successifs, selon un algorithme décrit un peu plus loin.
Le premier battage intervertit les deux premières cartes, le second battage mélange les quatre premières cartes, le troisième les six premières cartes, etc.

Aux étapes n = 1, 2, 3 ... on mélange les n premiers éléments de la suite avec les n suivants en les alternant :
le n + k-ième élément de l'ancienne suite est suivi du k-ième, pour k variant de 1 à n.
Ensuite, les éléments à partir de N = 2n+1 restent inchangés.

La carte X est toujours la carte qui se trouve à la X-ième place du paquet initial

Les positions de certaines cartes changent à chaque battage, d'où les notations :
La carte X de position initiale X (ou x₀=X) prend ensuite les positions x₁ = t₁(x₀), x₂ = t₂(x₁) ...
t₂ désignant le 2-ième battage et x₂ la place occupée juste après ce battage.

Tout naturel apparaît à la première place de l'une de ces suites.
(on a, dans l'ordre, 1, 2, 3, 1, 6, 5, 9, 1, 4, 2, 16 ... à la 1-ère place : Sloane A035485)

Le programme permet d'observer les étapes de ce mélange en cliquant sur [suivant].


Pour obtenir les positions successives t_n[k] d'un élément particulier n (carte) aux étapes k, entrer la valeur n de cet élément et cliquer sur [trajectoire].
L'image de droite donne la trajectoire de la carte 80 jusqu'à son arrivée à la première place.
Programme C de recherche de trajectoire.

Le bouton [premier] indique à quelle étape l'élément n apparaît pour la première fois en première position.

Lorsque cette valeur est très élevée (pour 54 c'est 252992198) il faut attendre un certain temps !
La liste de ces éléments records est 1 3 4 7 13 15 39 43 54 1227 1796 2674 3464 8206 17526 19704 23302 31965 32105 ...

Attente avant la 1ère place.

Quelle est la position initiale de la carte qui se retrouve au sommet, à l'étape n ?


Éléments x₀ qui seront à la 1ère place à l'étape n. Programme C correspondant.

La carte 37 du jeu initial se retrouve au sommet à l'étape 25. En entrant la valeur 25 ci-dessus et en cliquant le bouton [position initiale] on obtient la position 37.
Essayer de même 349 ou 1085.