Tri de 9 numéros avec 9 flips

Question

Vous souhaitez trier une séquence de nombres par ordre croissant. Vous pouvez effectuer des flips: prenez une sous-séquence de 4 nombres (a, b, c, d) et inversez leur ordre pour obtenir (d, c, b, a). Pouvez-vous trier la séquence suivante en 9 flips?

9 8 7 6 5 4 3 2 1

Answer 1

J'ai utilisé un ordinateur; si vous considérez que la triche, veuillez ignorer cette réponse:

12 solutions:

[9 8 7 6 5 4 3 2 1] [6 7 8 9 5 4 3 2 1] [6 5 9 8 7 4 3 2 1] [6 5 4 7 8 9 3 2 1] [6 5 4 7 8 1 2 3 9] [6 5 4 7 3 2 1 8 9] [6 5 4 1 2 3 7 8 9] [1 4 5 6 2 3 7 8 9] [1 2 6 5 4 3 7 8 9] [ 1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [6 7 8 9 5 4 3 2 1] [6 7 8 3 4 5 9 2 1] [6 7 8 3 2 9 5 4 1] [6 7 8 3 2 1 4 5 9] [6 7 1 2 3 8 4 5 9] [6 3 2 1 7 8 4 5 9] [1 2 3 6 7 8 4 5 9] [1 2 3 4 8 7 6 5 9] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 5 6 7 8 4 3 2 1] [9 5 4 8 7 6 3 2 1] [9 5 4 8 7 1 2 3 6] [9 5 4 8 3 2 1 7 6] [9 5 4 1 2 3 8 7 6] [1 4 5 9 2 3 8 7 6] [1 2 9 5 4 3 8 7 6] [1 2 3 4 5 9 8 7 6] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 5 6 7 8 4 3 2 1] [7 6 5 9 8 4 3 2 1] [7 6 5 3 4 8 9 2 1] [7 6 5 3 2 9 8 4 1] [7 6 5 3 2 1 4 8 9] [7 6 1 2 3 5 4 8 9] [7 3 2 1 6 5 4 8 9] [1 2 3 7 6 5 4 8 9] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 8 4 5 6 7 3 2 1] [9 8 4 5 6 1 2 3 7] [9 8 4 5 3 2 1 6 7] [9 8 4 1 2 3 5 6 7] [1 4 8 9 2 3 5 6 7] [1 2 9 8 4 3 5 6 7] [1 2 3 4 8 9 5 6 7] [1 2 3 4 8 7 6 5 9] [ 1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 8 4 5 6 7 3 2 1] [9 6 5 4 8 7 3 2 1] [4 5 6 9 8 7 3 2 1] [4 5 6 3 7 8 9 2 1] [4 5 6 3 2 9 8 7 1] [4 5 6 3 2 1 7 8 9] [4 5 1 2 3 6 7 8 9] [4 3 2 1 5 6 7 8 9] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 8 7 3 4 5 6 2 1] [9 8 7 3 2 6 5 4 1] [9 8 7 3 2 1 4 5 6] [9 8 1 2 3 7 4 5 6] [9 3 2 1 8 7 4 5 6] [1 2 3 9 8 7 4 5 6] [1 2 3 4 7 8 9 5 6] [1 2 3 4 5 9 8 7 6] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 8 7 3 4 5 6 2 1] [3 7 8 9 4 5 6 2 1] [3 4 9 8 7 5 6 2 1] [3 4 5 7 8 9 6 2 1] [3 4 5 7 8 1 2 6 9] [3 4 5 7 6 2 1 8 9] [3 4 5 1 2 6 7 8 9] [1 5 4 3 2 6 7 8 9] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1 ] [9 8 7 6 2 3 4 5 1] [9 8 7 6 2 1 5 4 3] [9 8 1 2 6 7 5 4 3] [9 6 2 1 8 7 5 4 3] [1 2 6 9 8 7 5 4 3] [1 2 6 5 7 8 9 4 3] [1 2 6 5 4 9 8 7 3] [1 2 6 5 4 3 7 8 9] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 8 7 6 2 3 4 5 1] [9 8 7 4 3 2 6 5 1] [4 7 8 9 3 2 6 5 1] [4 3 9 8 7 2 6 5 1] [4 3 2 7 8 9 6 5 1] [4 3 2 7 8 1 5 6 9] [4 3 2 7 6 5 1 8 9] [4 3 2 1 5 6 7 8 9] [ 1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 8 7 6 5 1 2 3 4] [9 8 1 5 6 7 2 3 4] [9 6 5 1 8 7 2 3 4] [1 5 6 9 8 7 2 3 4] [1 5 6 2 7 8 9 3 4] [1 5 6 2 3 9 8 7 4] [1 5 6 2 3 4 7 8 9] [1 5 4 3 2 6 7 8 9] [1 2 3 4 5 6 7 8 9]

[9 8 7 6 5 4 3 2 1] [9 8 7 6 5 1 2 3 4] [9 8 7 6 3 2 1 5 4] [9 8 7 1 2 3 6 5 4] [1 7 8 9 2 3 6 5 4] [1 2 9 8 7 3 6 5 4] [1 2 3 7 8 9 6 5 4] [1 2 3 7 8 4 5 6 9] [1 2 3 7 6 5 4 8 9] [1 2 3 4 5 6 7 8 9]

Avec le recul, nous pouvons construire une solution à la main:

un voyage sont trois retournements d'affilée:
un voyage ascendant: [1 2 3 4 5 6] [4 3 2 1 5 6] [4 5 1 2 3 6] [4 5 6 3 2 1] échange deux triplets et aussi renverse celui qui monte.
un voyage vers le bas: [1 2 3 4 5 6] [1 2 6 5 4 3] [1 4 5 6 2 3] [6 5 4 1 2 3] échange deux triplets et inverse également celui qui descend. Il est maintenant facile de voir que l'on peut combiner trois trajets, par exemple le trajet le plus à gauche possible avant et après le trajet le plus à droite possible pour former une solution.