October 1998
<<September October November>>
You must help Pete the pancake chef! He's desperately trying to sort his pancakes by size. How many flips will it take?
There is a stack of N pancakes -- each one a different size -- on top of the griddle. Your goal is to get the pancakes in a stack arranged by size, with the largest pancake on the bottom, smallest one on top. You must accomplish this by flipping the pancakes a limited number of times.
For each flip, you must (on Pete's behalf):
Choose a number k between 1 and N. Pick a pancake in the kth position (counting from the topmost pancake) and insert your spatula under it (between the pancakes in position k and (k+1). Then flip the pancakes on your spatula, reversing the order.
Example:
N=5 (Numbers on the pancakes represent the size of the pancake, not its position.) The smallest pancake is labeled "1":
Initial position: Top 1 3 5 2 4 Griddle
First move (k=3)
Yields: Top 5 3 1 2 4 Griddle
Second move (k=5) Yields: Top 4 2 1 3 5 Griddle
Third move (k=4) Yields: Top 3 1 2 4 5 Griddle
Fourth move (k=3) Yields: Top 2 1 3 4 5 Griddle
Fifth move (k=2) Yields: Top 1 2 3 4 5 Griddle
We used 5 moves to sort the stack.
Here's what we want you to tell us:
-
For a given N, what is the least number of flips with which you can guarantee that you will correctly sort the stack?
For every N, for every initial position, can it be done in N flips?
How many flips could be required for a given N and the worst possible initial position?
In other words, if we consider N to be fixed, for each initial permutation, there is some minimum number of flips that works. Find the maximum of these minima as you vary the permutations, i.e. find a hardest permutation.
E.g. if N=5, the permutation (Top 2,1,3,4,5 Griddle) would require only one flip, although you could take a roundabout path and take 13 flips. The minimum for this permutation is 1. The minimum for the permutation (Top 1 3 5 2 4 Griddle) is 5 flips as shown. It turns out that any other permutation can also be done in 5 flips. So 5 is the answer we're looking for here.
Or, to put this in simple mathematical terms: For N=number of pancakes, p=permutation Let f(N,p) be the minimum number of flips when faced with initial permutation p; let g(N) be the maximum of f(N,p) over choices of p. Find g (N).
FYI: Although this problem may appear simple at first, the solution is actually fairly complex.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
10/01/98 @ 12:00 AM EST
Solution:
11/01/98 @ 12:00 AM EST
List Updated:
11/15/01 @ 10:00 AM EST
People who answered correctly:
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.