Maths in a minute: Flipping pancakes

It's pancake day, so let's imagine a stack of pancakes. Unless you are very good at making them, the pancakes are likely to come in different sizes, which makes a stack of them look very untidy. One way of making it look better is to order them by size, so you have the biggest at the bottom and the smallest on the top.

How can you order the pancakes in this way if the only tool you have is a spatula you can use to flip the pancakes over? One method goes as follows. First number the pancakes by size; 1 for the smallest, 2 for the second smallest, and so on. Then find the first pancake (counting from the top of the stack) that is in the wrong place (i.e. has smaller pancakes beneath it). For example, you might find that pancake number 3 is in position number 2. Now insert your spatula beneath the offending pancake and flip the whole stack on top of the spatula over. The offending pancake is now right on top. Next, insert your spatula beneath the position where the offending pancake is meant to be (position 3 in our example) and again flip the stack on top of the spatula. The offending pancake is now in the position it is meant to be in.

If you keep going like this, for each offending pancake in turn, you will eventually end up with a stack that is sorted by size. And it turns out that if you have $n$ pancakes in total, this method takes at most $2(n-1)$ flips. This is good to know, but it still means that you might need a lot of flipping. For a stack of $n=10$ pancakes, it might take you all of $2\times 9 = 18$ flips, which is tedious. Is there a better method and, if yes, how many flips will it require?

That's a very tricky question. The first significant improvement on the upper bound of $2(n-1)$ was proved by non other than Bill Gates, together with Christos Papadimitriou, when Gates was a student at Harvard in the mid 1970s. The two proved that every stack of pancakes can be sorted by at most $(5n+5)/3$ flips. This bound was not improved until 2009 by a team of seven researchers from the University of Texas at Dallas, who divided the problem into 2220 different cases to show that every stack can be sorted by at most $18n/11$ flips.

In 2011 another team of researchers showed that the problem of finding the shortest sequence of flips for a given stack of pancakes is what's called NP-hard. Loosely speaking it means that, as far as anyone knows, the problem really is very, very hard. For more detail on what it means in the technical sense, see this article.

The pancake flipping problem isn't just relevant to pancakes, but finds applications in all sorts of contexts where things need to be sorted. For an example involving chromosome flipping and evolution, see this article.