In this series of articles, I’m writing about mathematical questions we don’t know the answer to – which haven’t yet been proven or disproven. This edition is a topical one, for Pancake Day (Shrove Tuesday, celebrated in the UK this year on 9th February).

Some of the best mathematical teasers are those which originate in a real-world problem – although the problem for pure mathematicians is that that happens much less often than it does for applied mathematicians, who are presented with interesting real-world problems all the time. That’s why it’s especially nice when a more pure one pops up, and that’s exactly what happened to mathematician Jacob E Goodman, back in 1975.

Goodman was trying to sort a pile of towels without having anywhere else to put them – he could only lift the top part of the stack, flip it over, and put it back down onto the same stack. He realised that this was exactly the same question as the mathematical problem of sorting a sequence by repeatedly taking different lengths of the first section (a prefix) of the sequence and reversing its order.

Sorting algorithms – ways to systematically put a set of objects into an order – are a hugely interesting mathematical area, and this was a particular subset of the question – you’re only allowed to take the first, or top, section of the pile, and reverse it. Goodman wanted to share this interesting puzzle he’d found, and wrote about it for the American Mathematical Monthly.

He realised a more accessible presentation of the problem was as a stack of differently sized pancakes, sent out by a careless chef in random order, and a harried waiter (Goodman submitted the article under the pseudonym Harry Dweighter, LOL) who can only fix this by using his one spare hand to put a spatula under the top section of pancakes and flip the whole thing.

As a simple example, a stack of three pancakes could come out in any one of six possible orders – shown below. One of these is of course the correct order, and two of them can be fixed in exactly one flip. A further two of the combinations require at least two flips to fix, and there’s one tricky one which takes three flipping operations to repair.

This means the ‘pancake number’ for three pancakes, is three – that’s the minimum number of flips needed to correct the most disordered stack of pancakes. (This is one of those tricky maximum minimums that are sometimes difficult to get your head around – it’s the largest number of flips you’ll need if you always do it in the most efficient possible way).

The question then became, what is the pancake number generally? It turns out this is a tricky question. We still don’t have a general formula for the pancake number for $n$ pancakes; we know the pancake number for various $n$, but the question remains unanswered for values of $n$ as small as 20 – the pancake number for 20 pancakes is still an open problem.

(*according to Simon Singh)

Many people have piled in to the problem – from maths giants like John Conway, to Bill Gates (yes, actually that Bill Gates). So far, we’ve managed to establish an upper and lower bound on the pancake number – for $n$ pancakes, $p(n)$ is between $\frac{15n}{14}$ and $\frac{18n}{11}$ (the upper bound being originally proved as $\frac{5n+5}{3}$ by Bill Gates and Christos Papadimitriou, in 1979 (PDF), and improved to its present value in 2009 by researchers at the University of Texas).

There is a simple algorithm for sorting a given stack – if you put your spatula under the largest pancake that’s not in its proper place, flip it to the top, then on your next flip, put it where it should be, and repeat these two moves, this will require at most $2n-3$ flips – although it’s unlikely to be optimal.

How many flips does it take to sort this stack of 6 pancakes?

In 2015, the problem of determining the minimal number of moves for a given stack was proven to be NP-hard by a team at the University of Nantes. As well as being a lovely open problem, it’s a great example of a food-based (or towel-based) mathematical problem which has real utility – it’s recently been shown to have applications in parallel processing, providing an effective routing algorithm between processors.

As usual, CLP has been inspired to make a web gadget, so you can play with pancakes:

Sack the Chef – The Burnt Pancake Problem

It gets worse though. As well as being terribly lax about the order in which he plates up the pancakes, the chef has now also burnt every single one of them on one side. The waiter’s sorting task has become much more complex, as each pancake needs to be put in order, but with the burnt sides still facing down.

This problem is known as the Burnt Pancake Problem, and also has its own celebrity special guest – Futurama and Simpsons writer David S Cohen published a paper in 1992, On the Problems of Sorting Burnt Pancakes, with his Berkeley colleague Manuel Blum.

Cohen and Blum worked out the Burnt Pancake Number has an upper bound of $\frac{3n}{2}$, and a lower bound of $2n-2$. They conjectured that the most difficult configuration to sort in this case is the one in which the pancakes are in the correct size order, but each of them is upside down, and proved that this can be sorted in $\frac{23n}{14}$ flips (later improved by the team in Texas to $\frac{3(n+1)}{2}$). Since any solution to a burnt stack is also a solution to the equivalently ordered unburnt stack, proving this conjecture would actually improve the bound on the unburnt problem.

This problem clearly has something fascinating about it, given all these celebrity researchers. But it even turns out that humans are not the only creatures to have worked on the pancake problem. A team of (human) researchers in 2008 worked out a way to use bacteria, capable of cutting out and flipping around sections of DNA inside living cells, to compute answers to the burnt pancake problem.

The team used E. Coli bacteria, and DNA recombination, on sections of DNA that represented simple stacks of pancakes (burnt on one side, since DNA has an orientation). The sequences were designed so that bacteria which had correctly sorted its DNA into the right order would become antibiotic resistant, and the huge numbers of bacteria present effectively performed massively parallel processing to crunch through the possibilities and find the most efficient sequence of flips. As a method of computation, it’s good, but it does produce antibiotic resistant bacteria, so it’s probably not the best.

So, if you’re serving pancakes for dinner today, and you find they all come out different sizes (or if you burn all of them on the bottom), don’t despair – see if you can flip them all into a perfect stack, using mathematics.

More information

Pancake Sorting, at Wolfram Mathworld

Flipping pancakes with Mathematics, Simon Singh, The Guardian (Nov 2013)

A slightly hypnotic visualisation of pancake sorting, on YouTube

The Pancake Problems, at Douglas B West’s index of open problems in graph theory and combinatorics

Pancake Flipping-related sequences on the OEIS

CLP’s pancake flipping gadget