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

*n*th pancake number, P

*. For five pancakes, for example, no more than five flips are ever needed, so P*

_{n}_{5}= 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

*had to be at least*

_{n}*n*and no more than 2

*n*– 3, for

*n*greater than 2.

In 1979, William H. Gates and Christos H. Papadimitriou improved on the upper and lower limits, showing that (5

*n*+ 5)/3 flips always suffice and that 17

*n*/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 15

*n*/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."

## 4 comments:

I greatly enjoyed your recent MAA Online article on "Pancake sorting" and was pleasantly surprised to recognize the nice "pancake" metaphor as the basis of an early computer game we named "Reverse" that was created popularized at "People's Computer Company" and published back in May 1973!

See http://www.svipx.com/pcc/gameslist.html

I don't have access to the old newsletter right now, so don't know if we mentioned it, but I'm sure we were aware of the easy N and 2N-3 bounds at the time, and the fact that sharper general bounds might be "glitchy" based on our observations for small N.

I have often idly wondered about what we called the "diameter of the Reverse move graph" over the years, but was unaware until your article that anybody else had ever been interested in it, nor that Bill Gates had worked on it!

Thanks for the fascinating update!

We ran a programming contest on this problem in 2004:

http://recmath.org/contest/Pancakes/index.php

At this occasion, we computed the pancakes up to N=14:

http://tomas.rokicki.com/pancake/

And I posted a message after having finished N=15, with a cluster of 10 computers:

http://tech.groups.yahoo.com/group/AlZimmermannsProgrammingContests/message/1275

http://tech.groups.yahoo.com/group/AlZimmermannsProgrammingContests/message/1276

The solutions for N=15 are here:

http://euler.free.fr/pancakes/Sol15.zip

I never completed N=16, because of boredom (and my cluster was colleagues' computers, and they needed their computers).

BTW, Tomas listed all the hardest pancakes known here:

http://tomas.rokicki.com/pancake/witnesses.html

JC

So how is (18/11)n an improvement over (15/14)n for an

Upperbound? 18/11 is greater than 15/14, last I checked.Dear,

18/11 is an improvement over 5/3 for UPPER bound.

15/14 is a lower bound which is an improvement over 17/16 as proposed by Gates et. al.

Upper bounds with smaller values and lower bounds with higher values are what we seek.

Regards.

___________________________________

Anonymous said...

So how is (18/11)n an improvement over (15/14)n for an Upper bound? 18/11 is greater than 15/14, last I checked.

11:34 AM

Post a Comment