Assume that  numbered pancakes are stacked, and that
a spatula can be used to reverse the order of the top  pancakes for  . Then the pancake sorting problem asks
how many such "prefix reversals" are sufficient to sort an arbitrary stack
(Skiena 1990, p. 48).
The maximum numbers of flips  needed to sort
a random stack of  , 2, 3, ... pancakes are 0, 1, 3, 4,
5, 7, 8, 9, 10, 11, 13, ... (Sloane's A058986), with the number of maximal stacks for  , 3, ... being
1, 1, 3, 20, 2, 35, 455, ... (Sloane's A067607).
The following table (Sloane's A092113) gives the numbers of stacks of  pancakes requiring
 flips. A flattened version is shown above as a
binary plot.
 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | 1 | 1 | | | | | | | | | | 2 | 1 | 1 | | | | | | | | | 3 | 1 | 2 | 2 | 1 | | | | | | | 4 | 1 | 3 | 6 | 11 | 3 | | | | | | 5 | 1 | 4 | 12 | 35 | 48 | 20 | | | | | 6 | 1 | 5 | 20 | 79 | 199 | 281 | 133 | 2 | | | 7 | 1 | 6 | 30 | 149 | 543 | 1357 | 1903 | 1016 | 35 |
For example, the three stacks of four pancakes requiring the maximum of four flips are  ,  , and  , which can be ordered using the flip sequences
 ,  , and  , respectively (illustrated above). Similarly,
the two stacks of six pancakes requiring the maximum of seven flips are  and
 , which can be ordered using the flip
sequences  and  ,
respectively.
It is known that  for  ,  if
 is a multiple of 16, and  .
Berman D. and Klamkin, M. S. "A Reverse Card Shuffle." SIAM Rev. 19,
739-741, 1977.
Cohen D.S. and Blum, M. "On the Problem of Sorting Burnt Pancakes." Discr.
Appl. Math. 61, 105-120, 1995.
Dweighter, H. "Problem E2569." Amer. Math. Monthly 82, 1010,
1975.
Garey, M. R.; Johnson, D. S.; and Lin, S. Amer. Math. Monthly 84,
296, 1977.
Gates, W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal."
Discr. Math. 27, 47-57, 1979.
Györi, E. and Turán, G. "Stack of Pancakes." Studia Sci.
Math. Hungar. 13, 133-137, 1978.
Heydari M. H. and Sudborough, I. H. "On the Diameter of the Pancake
Network." J. Algorithms 25, 67-94, 1997.
Morales L. and Sudborough, I. H. "A Quadratic Lower Bound for Reverse Card Shuffle." Presented at 26th S.E. Conf. Comb. Graph Th. Computing. Preprint 1995.
Pegg, E. Jr. "Pancake Sequence." http://www.mathpuzzle.com/pancakes.htm.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory
with Mathematica. Reading, MA: Addison-Wesley, 1990.
Sloane, N. J. A. "My Favorite Integer Sequences." In Sequences and Their Applications (Proceedings of SETA '98) (Ed. C. Ding, T. Helleseth,
and H. Niederreiter). London: Springer-Verlag, pp. 103-130, 1999. http://www.research.att.com/~njas/doc/sg.pdf.
Sloane, N. J. A. Sequences A058986, A067607, and A092113 in "The On-Line Encyclopedia of Integer Sequences."
West, D. B. "The Pancake Problems (1975, 1979, 1973)." http://www.math.uiuc.edu/~west/openp/pancake.html.
|
Contact the MathWorld Team
