October 1998
<<September October November>>
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