Ce casse-tête est un succédané du jeu de taquin. Il est encore plus économique car il suffit d'une feuille de papier, d'un crayon et d'une gomme. On écrit sur N cases alignées sur un axe horizontal les nombres entiers consécutifs N,N-1,N-2,...,4,3,2,1 dans l'ordre décroissant . Il s'agit de restituer ces mêmes entiers dans l'ordre croissant 1,2,3,..,N-1,N en utilisant la règle suivante :

On choisit un nombre k et on le déplace de k cases. Si on arrive en bout de chaîne avant d'avoir fini le déplacement, on poursuit à partir de la première case. A la fin du déplacement, le nombre occupe sa case d'arrivée et le nombre qui occupait précédemment cette case est transféré sur la case laissée libre par le nombre déplacé.

Exemple : on a la position suivante 6,8,2,7,1,4,5,3. On choisit de déplacer le chiffre 7. On compte 1,2,3 et 4 et on arrive en bout de chaîne. On compte 5,6,7 à partir de la première case et on arrive à la case occupée par le 2. D'où la nouvelle configuration 6,8,7,2,1,4,5,3.

Commencer le casse-tête avec les petites valeurs de n=2,3,4,5,6,7,8..  en essayant de minimiser le nombre de déplacements. Trouver une loi générale donnant le nombre minimal de déplacements pour remettre en ordre croissant la séquence des entiers N à 1 écrits en ordre décroissant.

 Solution