On écrit les 8 premiers nombres entiers dans l'ordre croissant : 1, 2, 3, 4, 5, 6, 7, 8. On veut les réarranger dans l'ordre décroissant 8, 7, 6, 5, 4, 3, 2, 1 en adoptant la règle suivante :

Deux chiffres quelconques peuvent être mutés à condition qu'après échange l'écart entre chacun des deux chiffres et les (ou le) chiffre(s) voisins n'excède pas 3.Par exemple ,dans la séquence initiale, on peut échanger 2 et 4 car la séquence 1,4,3,2,5,6,7,8 obéit à la règle. A l'inverse on ne peut pas échanger 2 et 5 car dans la séquence 1,5,3,4,2,6,7,8 l'écart entre 1 et 5 commet celui entre 2 et 6 sont égaux à 4 et dépassent 3.

Comment réaliser la nouvelle séquence décroissante en un minimum d'échanges ?

Source : Jaime Pontachik - Puzzlers' Tribute, A Feast for the Mind

 Solution