Source: Saurabh Joshi's Blog
Problem: (copy-pasting from the source)
Suppose we have 13 cards arranged in descending order: K Q J 10 9 8 7 6 5 4 3 2 1
At any move, you can take a substring of cards and move it elsewhere. For example, 10 9 8 could be move to the right by 2 steps to get K Q J 7 6 10 9 8 5 4 3 2 1. The goal is to sort the string in increasing order minimize the number of such moves.
It must be absolutely obvious that you can do it with 12 moves but the very fact that I’m asking you this question means that you can do better. How many moves do you need?
Now the obvious extension to this problem is to generalize this technique for any n.
Update (Sep 07, 2010):
Solution: At Saurabh Joshi's blog (Link)