5
$\begingroup$

You want to sort a sequence of numbers into ascending order. You can perform flips: take a sub-sequence of 4 numbers (a, b, c, d) and reverse their order to obtain (d, c, b, a). Can you sort the following sequence in 9 flips?

9 8 7 6 5 4 3 2 1

$\endgroup$

1 Answer 1

4
$\begingroup$

I used a computer; if you consider that cheating pls ignore this answer:

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]

With the benefit of hindsight we can construct a solution by hand:

a trip are three flips in a row:
an up trip: [1 2 3 4 5 6] [4 3 2 1 5 6] [4 5 1 2 3 6] [4 5 6 3 2 1] swaps two triplets and also reverses the one that moves up.
a down trip: [1 2 3 4 5 6] [1 2 6 5 4 3] [1 4 5 6 2 3] [6 5 4 1 2 3] swaps two triplets and also reverses the one that moves down. It is now easy to see that we can combine three trips for example the leftmost possible up trip before and after the rightmost possible down trip to form a solution.

$\endgroup$
4
  • $\begingroup$ Nice work! It is not cheating, but I was hoping that this puzzle is small enough to be solved by hand. Would you be able to format your answer so that there is a clear separation between different solutions. BTW are these all the possible solutions? $\endgroup$ Commented Sep 22, 2020 at 2:26
  • 1
    $\begingroup$ @DmitryKamenetsky Done. Yes, these are all solutions with precisely 9 flips and without immediate cancellation (i.e. twice the same flip next to itself). $\endgroup$ Commented Sep 22, 2020 at 2:32
  • $\begingroup$ @DmitryKamenetsky I added a "by-hand" solution. $\endgroup$ Commented Sep 22, 2020 at 2:47
  • $\begingroup$ Very nice Paul! $\endgroup$ Commented Sep 22, 2020 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.