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 1234...in 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
2 comments:
31542
13542 flip top two
45312 flip top four
54312 flip top two
21345 flip all five
12345 flip top two
(flips them in five flips)...
So the flipping process can take advantage of the configuration of the entire stack and it is not necessarily optimum to put the biggest pancake on the bottom first. Adding a pancake does not add one more layer to the process, but in some cases it will provide the freedom to take a shortcut.
Does this problem lend itself to induction in a more subtle manner than what I so cavalierly and incorrectly assumed?
This reminds me of a card "game" that I saw in an article by Martin Gardner many years ago. In actual fact, the game is really another look at the same thing.
You take all cards of one suit (say Spades) and shuffle them. Then you turn the stack face up. Let's say the top card is a 5; you deal off five cards, one by one, and put them back on your stack (in essence "flipping" the top five "pancakes.") Whatever the new card showing, you now flip that many cards. When the card showing is an Ace (counted as a one), of course the game is over.
There are all kinds of associated probability questions, such as: What is the probability that following the sequence will result in a perfect K through Ace arrangement once the Ace is on top? What's the maximum number of moves possible for a given stack? IS there a maximum, or is it possible to have a stack that would keep going in a "loop" under the given instructions?
Answer to that one: it's not possible; the game will always reach an end. The proof, which I thought was quite clever, involved assigning each arrangement a "value" based on binary powers of the cards in "correct" positions. In other words, if the five is in the correct position—fifth card down from the top—that's worth 2^5, or 32. If the King is on the very bottom of the stack—13th position—that's worth 2^13. Then it can be noted that a move from any arrangement will always increase the "value" of the stack, and also it is noted that there is a maximum value for all the cards.
The cards may serve as a useful model for this pancake problem as well.
Post a Comment