Ponder This Challenge - October 1998 - Sorting pancakes

Ponder This Challenge:

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

Solution

• Click here to view the solution

  We don't know the complete answer to this.

  Let f(N) be the least number of flips guaranteed to bring any initial permutation of N pancakes into the proper order. We will see below that f(N) is between N and 2N -3.

  If N is at least 4 we know that f(N) is at least N. To see this, count the number of instances where pancakes k and k+1 (or pancake N and the griddle) are adjacent; call them "good pairs". Start with a permutation like (1,3,5,2,4) (if N is odd) or (2,4,6,1,3,5) (if N is even); such a permutation has no good pairs.Each flip can bring only one pair of pancakes into contact (or bring the largest pancake into contact with the griddle), so that the number of good pairs increases by at most 1. Since we want to end up with N good pairs (1,2), (2,3), ..., (N-1,N) and (N,griddle), it must require at least N flips to do so.

  But some permutations can require more than N flips. The permutation 536142 -> 123456 requires at least 7 flips, showing that f(6) is at least 7. (In fact f(6)=7.)

  For an upper bound of 2 N -3, follow this procedure. Find the largest pancake and with one flip bring it to the top. Then flip the whole stack, putting that largest pancake onto the griddle. Now sort the remaining N -1 pancakes. It took us two flips to put pancake N into its proper position, another two to put N-1 into position, and so on, until we have put pancake 3 into position (using 2 N -4 flips so far). We are left with two pancakes, which can be sorted with at most one flip, bringing our total to 2 N -3 at most.

  Gates and Papadimitriou (Discrete Math 27 pp. 47-57, 1979) have shown tighter bounds: (17N /16) < f(N) < (5 N /3).

  This problem originally appeared in the American Mathematical Monthly in 1975, submitted under the pseudonym "Harry Dweighter".

  The most recent work on the subject appears to be "On the Diameter of the Pancake Network," by M. Heydari and I. H. Sudborough, Journal of Algorithms, 25 (1997), pp. 67-94. These authors obtain a better lower bound (15N/14), and also consider the problem of burnt pancakes, where each pancake must have its lighter side facing up.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers