Using your Head is Permitted

September 2008 riddle

This month's riddle comes from Rani Hod.

Consider a permutation over the numbers 1 through n. For example, with n=7, one can think of the permutation [1, 4, 5, 6, 2, 3, 7].

Let us define a Block Move as a function that makes a new permutation from an existing permutation by taking a contiguous block from it and placing it in a new position. The permutation given above, for example, can be made into the permutation [1, 2, 3, ..., 7] by a single block move. All we need to do is to take the block "4, 5, 6" and move it to be between the "3" and the "7". We say that the original permuation can be sorted in 1 block move.

Not all permutations are this easy to sort. The permutation [4 3 2 1 5 13 12 11 10 9 8 7 6], for example, was shown by help from a computer to require at least 8 block moves to be sorted.

This month's riddle is regarding sorting the inverse permutation [n, n-1, ..., 3, 2, 1]. Answer the following question:

How many block moves does it take to sort the inverse permutation (as a function of n)?

To demonstrate the correctness of your answer, prove that the number you give is a minimum bound and describe an algorithm that sorts in this number of block moves.

List of solvers:

Sen Gu (2 September 06:55)
Bojan Bašić (6 September 06:30)
Sun Yixun (6 September 15:33)
Dan Dima (26 September 13:16)
Marcos Simões (30 September 04:18)
Itsik Horovitz (30 September 19:05)

Elegant solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page