Flipping pancakes with mathematics

(Written by Simon Singh at the The Guardian online on 14th November 2013. Simon Singh is the author of The Simpsons and Their Mathematical Secrets)

Mathematical minds love a problem that's easy to pose but tough to solve.

Tomorrow marks the 80th birthday of Jacob E Goodman, a mathematician at the City College of New York. If Professor Goodman's name does not ring any bells, then maybe you know him better by his pseudonym, Harry Dweighter. No? Confused? Wondering why a mathematician needs to disguise his identity? Allow me to explain.

In around 1975, Goodman was at home folding towels for his wife. The final pile was somewhat messy, so he decided to restack the folded towels in order of size, smallest folded towel at the top, biggest at the bottom. The problem was that there was no room for a second pile, so he was forced to flip over the top few towels, reassess the situation, then flip over a few more from the top, and so on.
He recalls how a curious problem crossed his mind: "How many flips would I need in the worst case? I thought it was interesting enough to send to the American Mathematical Monthly, but a more 'natural' setting seemed to be pancakes."

Thus the so-called pancake sorting problem was born. How many flips are required to turn a disordered stack of pancakes into an ordered stack?

Goodman was still building his reputation as a mathematician and did not want others to think that he was only interested in trivial pancake puzzles, so he adopted a false identity: "It was easy enough to come up with the jocular pseudonym Harry Dweighter ("harried waiter"), but what if the American Mathematical Monthly wanted to contact me in connection with publishing the problem? I told the secretaries at the department that any calls for Harry Dweighter should be diverted to me. I decided that if I ever had to call anyone back at the Monthly, I would pronounce Dweighter as Dwight-er, so as to deflect suspicion."

This is how the problem was posed: The chef in our place is sloppy, and when he prepares a stack of pancakes they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, down to the largest at the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (as a function of n) that I will ever have to use to rearrange them?

To understand the problem, we can try to work out the number of flips required for three pancakes. The three pancakes can arrive in one of the following six arrangements, and alongside each stack is the number of flips required to put them in the right order.



pancake flipping Illustration: Simon Singh


The first stack is trivial, because it arrives in the correct order, hence zero flips. The second stack requires just one flip, with a spatula placed above the lowest pancake. The sixth stack requires three flips – try and work out the flipping protocol – and this is worst case scenario. Hence, the pancake number for three pancakes is said to be three, ie, P3 = 3.

As the pile of pancakes grows, the problem becomes increasingly difficult as there are more and more possible starting arrangements, and an increasing number of possible flipping procedures; P17 = 19, P18 = 20, P19 = 22 and – as yet – nobody knows the number of flips required to reorder 20 pancakes in the worst case scenario.

The problem is simple to pose, yet tough to solve. Indeed, nobody is close to developing a general formula that predicts the number flips required for any given number of pancakes.

Mathematicians always like a deceptively difficult problem. Moreover, such flipping puzzles also have some interesting real world applications. For example, biologists are interested in flipping in the context gene sequences. Some organisms share the same genes, but in a different order, so scientists are keen to know how many flips would have been necessary to transform one sequence into the other.

Similarly, computer scientists are intrigued by the problem, because it has parallels with reordering disorganised data. Indeed, Bill Gates's only academic paper (pdf) is on the topic of pancake flipping. His co-authored paper proved an upper limit to the number of flips required to reorder n pancakes, namely (5n + 5) ⁄ 3 flips. Therefore, if you receive 100 pancakes, you will always be able to order them correctly in 166 or fewer flips.

My own interest in the problem was sparked when I was interviewing the writers of The Simpsons for my book The Simpsons and Their Mathematical Secrets. Many of the writers of The Simpsons have mathematical backgrounds and they frequently smuggle mathematics into the series. When talking to David X Cohen (a Simpsons writers and co-creator of Futurama), he casually mentioned that he had co-authored a paper titled, On the Problem of Sorting Burnt Pancakes.

In this version of the problem, the pancakes not only have to be in the correct size order, but they also need to be in the right orientation, with the burnt side facing down. Cohen's paper set the lower and upper bounds for burnt pancake flipping between 3n / 2 and 2n – 2. Hence, for 100 burnt pancakes, we know that the number of flips required to orient and order them in the worst case scenario is between 150 and 198.

It is worth noting that this is not Professor Goodman's only mathematical problem based on a household chore: "I was peeling potatoes with a swivel-bladed vegetable peeler. If you do this rapidly, you wind up with a convex body. So it's natural to ask what proportion of the original volume you can capture with an inscribed convex body." This inspired his 1981 paper titled, On the Largest Convex Polygon Contained in a Non-convex n-gon, Or How to Peel a Potato.

So, in the wake of his 80th birthday celebrations, perhaps we can expect new mathematical problems concerning the geometry of torn wrapping paper, the variability of birthday cake crumb size and the maximally efficient arrangement of cards on a finite horizontal surface.