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, ... (OEIS A058986), with the number of
maximal stacks for ,
3, ... being 1, 1, 3, 20, 2, 35, 455, ... (OEIS A067607).
The following table (OEIS 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.
Monthly82, 1010, 1975.Garey, M. R.; Johnson, D. S.;
and Lin, S. Amer. Math. Monthly84, 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. Algorithms25, 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.