2006 randonneurs marchent à la file indienne. Ils portent des dossards numérotés de 1 à 2006 et aucun d'eux n'a un rang qui coïncide avec le numéro de son dossard. On souhaite tous les placer dans l'ordre croissant des numéros. Les seules permutations possibles consistent à demander à tout couple de randonneurs d'échanger leur place à condition qu'ils soient voisins et qu'aucun d'eux ne soit déjà à sa place.
Exemple : avec une file de 5 randonneurs les positions initiales des dossards sont les suivantes: 2,4,5,3,1. La permutation (2,4) est possible car les deux randonneurs sont voisins et aucun n'est à sa place. On obtient ainsi la configuration : 4,2,5,3,1. Au tour suivant, les permutations (5,3) et (3,1) sont possibles mais les permutations (4,2) et (2,5) ne le sont pas car le deuxième randonneur est à sa place.

Est-ce possible de remettre les 2006 randonneurs dans l'ordre croissant des numéros?

Source : d'après Tournoi des villes 2002.

 Solution