Improved Pancake Sorting

You have a stack of pancakes, each one a different size. You want to rearrange the pancakes in order of size, with the smallest one on top and the largest on the bottom. But your only option is to insert a spatula at some point in the stack and flip the upper pancakes into reverse order. What's the maximum number of such flips that you'll ever need to sort the pancakes?

This classic mathematical problem, often described as pancake sorting or more formally as prefix reversal, has been around since 1975. Now, a team of computer science students has made the first improvement in nearly 30 years in one theoretical limit on solving the problem.

The maximum number of flips ever needed to rearrange a stack of n pancakes is known as the nth pancake number, P_n. For five pancakes, for example, no more than five flips are ever needed, so P₅ = 5.

Until recently, pancake numbers were known only up to n = 13.


In the last few years, teams of Japanese computer scientists have used clusters of computers to work out values for n = 14 to 17: "Computing the diameter of 17-pancake graph using a PC cluster."


Early on, researchers established theoretical bounds on pancake numbers. Initial work established that P_n had to be at least n and no more than 2n – 3, for n greater than 2.

In 1979, William H. Gates and Christos H. Papadimitriou improved on the upper and lower limits, showing that (5n + 5)/3 flips always suffice and that 17n/16 flips may be needed. Bill Gates, co-founder of Microsoft, had worked on the problem when he was a sophomore at Harvard, as described in a recent NPR story, and published the resulting paper, his only technical contribution to the mathematical literature, in collaboration with Papadimitriou, then a young professor at Harvard and now at the University of California, Berkeley. The paper, published in Discrete Mathematics, was titled "Bounds for sorting by prefix reversal."

In 1997, Mohammad H. Heydari and I. Hal Sudborough improved the lower bound to 15n/14.

In 2008, students at the University of Texas at Dallas, working with Sudborough, used a lot of computation to establish an improved upper bound, (18/11)n. A paper describing the results, "An (18/11)n upper bound for sorting prefix reversals," was published in Theoretical Computer Science (Vol. 410, no. 36, August 31, 2009, pp. 3372-3390). The authors are B. Chitturi, Bill Fahle, Zhaobing Meng, Linda Morales, Charles Shields, Hal Sudborough, and Walter Voit.

The effort took about two years. "Improving the upper bound for the pancake problem has challenged mathematicians and computer scientists for 30 years," Sudborough noted. "We succeeded through the dedicated efforts of our team, the willingness of all to devote many hours to analysis, verification, and innovation, and our overriding belief that a better bound could be discovered."