This article was originally published in the Winter/Spring 2016 edition of the MTCircular.
The Pancake Problem is a sorting problem with connections to computer science and DNA rearrangements, which leads to discussions of algorithms, sequences, and the usefulness of approximations and bounds. Te original problem was frst posed by mathematician Jacob Goodman under the pen name “Harry Dweighter” (read it quickly) in 1975, and it has delighted mathematics enthusiasts (including an undergraduate Bill Gates) ever since! I first learned of the problem during a talk by the mathematics writer Ivars Peterson, and recently facilitated a session on it at the Philadelphia Area Math Teachers’ Circle.
It is useful for each table to have at least four small disks of different sizes to simulate pancakes.
The Pancake Problem
The chef at the Philadelphia Area Mighty Tasty Cafe holds the record for making pancakes quickly. However, in her rush to get the pancake orders out to customers, she ignores how the stacks look as they leave the griddle. No two pancakes are the same size, and the chef tosses the pancakes directly from the griddle onto the plate. The waiter delivering the pancakes tries to rearrange the stacks on his way out of the kitchen, but since he is holding the plate in one hand and the spatula in the other, he is only able to make one type of move in his quest to adjust the stack: he can stick the spatula somewhere in the stack and flip, in one motion, everything that sits above the spatula. Figure 1 shows an example of a legitimate move. The waiter’s goal is for the stack of pancakes to increase in size from the top of the stack to the bottom, so by the time it gets to the customer it looks like a pyramid of pancakes. He notices that it is easier to do this for some stacks than for others. For example, occasionally the chef happens to hand him a plate where the pancakes are already in order, so he doesn’t need to make any flips. Other times it takes him several flips to get the pancakes in order.
The waiter wants to make sure he can deliver the pancakes before they get cold, so he would like to know the worst-case-scenario number of flips he’d have to perform on any given number of pancakes. We call this number the “Pancake Number,” and denote it by Pn, where n is the number of pancakes in the stack. At the Philadelphia Area Math Teachers’ Circle, we started with a group discussion investigating Pn for small n. For example, if a stack has only one pancake (n = 1), zero flips are needed, so P1 = 0. If n = 2, then the worst-case number of flips is one, to rearrange the stack with the larger pancake on top, so P2 = 1. It turns out finding Pn is a hard problem as n increases! The Pancake Number Pn is currently unknown for more than 19 pancakes.
Tackling Small Cases
At this point, we broke into small groups to work on calculating P3 and P4. One of the first ideas that groups discussed was how to succinctly represent pancake sizes within a stack. A few groups started with “S, M, L” (small, medium, large) for the stack of three, and then switched to a number representation (1, 2, 3, 4) once they started to work on four pancakes. As groups moved forward with the problem, they found they needed to discuss and demonstrate whether they were using an efficient flipping strategy for each new stack. Groups also discovered that, although there is a unique stack that requires the worst-case number of flips for n = 3, for each value of n larger than 3 there are several different stack configurations that require the worst-case number of flips. For example, for n = 4, there are three different configurations of pancakes that would require four flips to rearrange. What are they?
Further Leaps and Bounds
At this point, we challenged groups to come up with a general set of steps—an algorithm—for rearranging that would work on any stack of pancakes. We also asked how many steps this algorithm would take on n pancakes in the worst case.
One such algorithm is as follows: Find the largest pancake in the stack. Place the spatula under the largest pancake and flip so that it is now on the top of the stack. Next, place the spatula under the whole stack and flip so that the largest pancake is on the bottom. The second stage of this process is to find the second largest pancake and place the spatula under it. Flip so that it is now on the top. Place the spatula just above the largest pancake (below the top n-1 pancakes), and flip so that the second-largest pancake is now in the correct position. Repeat until all the pancakes are in the correct position. The worst-case number of flips for n pancakes using this algorithm is 2(n-2)+1=2n-3. Each pancake takes two flips to get in the correct position, except for the final two pancakes, which only require one flip.
This algorithm provides us with a ceiling, or an upper bound, for Pn for each n. Tis is useful because, even though we may not know Pn exactly, we know that the waiter would be able to rearrange any stack of n pancakes in at most 2n-3 flips. The waiter would be happy to hear this news, because it means even a large stack of pancakes can be delivered before his shift ends. Whether they would still be warm is unknown!
During our session, groups came up with the same upper bound through a recursive argument. Their logic: It takes two flips to get the largest pancake on the bottom of the stack, and after that you are dealing with only the upper stack of n-1 pancakes. Therefore, Pn is at most P(n-1)+2, when dealing with more than three pancakes.
A final question we discussed as a whole group was how to obtain a floor, or a lower bound, on Pn. The challenge is to come up with a configuration of pancakes that you know would take at least n flips, no matter which flipping strategy is used. Participants had ideas about the “worst” stacks based on their work with four pancakes, so we tried to come up with a worst-case stack for five pancakes, too. One idea was to have the stack as “deranged” as possible. For example, if the correctly ordered smallest-to-largest stack is represented by (1, 2, 3, 4), then the stack (2, 4, 1, 3) has none of the adjacencies of the final desired stack, including the plate being next to the largest pancake as one adjacency. It takes at least four flips to rearrange this stack. In general, it takes at least n flips to rearrange such a stack, because it takes at least one flip to fix each adjacency. This provides a lower bound for Pn.
Burnt Pancakes and Beyond
How many stacks of size n require a certain number of flips? For example, how many stacks of four pancakes require zero flips, one flip, two flips, etc.? There are many additional questions to investigate, including the “Burnt Pancakes” Problem Circle puzzle below.
If the pancakes are burnt on one side, the stack that gets sent out to the customer should not only be in order, but it should also have all the burnt sides facing down. What is the worst-case number of flips for two, three, and four burnt pancakes?
About The Author
Katie Haymaker is Associate Professor of Mathematics at Villanova University. This session was prepared with the cooperation of the Philadelphia Area Math Teachers’ Circle Leadership Team: Catherine Anderson, Steve Bartholomew, Kathy Boyle, Aimee Johnson, Amy Myers, Josh Sabloff, and Josh Taton.