Saturday, 28 February 2009

Pancakes on My Mind

There is a nice solution in the comments of my last post by Nate to show that the stack of pancakes never needs more than 2n-3 flips.... but then he adds, "The optimum (or most flippant) arrangement which would require the most flips could be found by working backward from the last flip. " .... hmmmmm, I wasn't sure, so I set about trying his theory will small stacks I probably wouldn't mess up... By Nate's method, there will be a stack of four pancakes with 2(4)-3 = 5 flips necessary... and using his inversion process, 1234, would be the fifth step, so 2134 was the previous, or fourth step, and 3124 the step before that. The second step would be 1324, and the first step would be to 4231, so we must have started at 2431... But it concerned me that I had no proof that the "flip the largest to the top, then flip the whole stack to get it on the bottom" method was ALWAYS the best strategy. For instance, if we start at 2431, we could flip the top three to get 3421. Then if we flip the top two, we would have 4321, and finally flipping the whole stack, we are home to only THREE moves, rather than five.

Now the shocker. Not only does the method not always produce the fastest results, the 2n-3 is an upper boundary on the number of flips, but it may not always be the maximum. I think it is for three pancakes, but it seems that for almost any other number of pancakes, you need less than 2n-3 for the most difficult stack.

After investigating furthur, it seems that 2n-3 is almost always more than the number of flips needed. At the Mathworld site, they have a nice table that shows the number of possible ways of stacking the pancakes that require any given number of flips to sort.

The table agrees that any stack of four needs no more than four flips, and even a set of five, needs no more than five flips... Which brings me back to Nate's creation. He thought that 31542 would take seven steps to sort, but the Wolfram site suggest it should not need more than five. So today's question, is can you do it in five ??? (or less???).. good luck
Post a Comment