4, 6, 8, 10, 12, 14,….What comes next?

The answer, naturally, is 15. If you’re talking about the Burnt Pancake problem, that is. (And the sequence actually starts 1, 4, 6, 8… but I left off the initial 1 because otherwise you would have known right away that something was amiss.)

The Burnt Pancake problem involves pancakes of different sizes, each with one burnt side, piled up on top of one another. Here’s how famous math guy and Emmy winner David X. Cohen initially described the problem in this interview with Sarah Greenwald:

The question was how do you sort these disks to get the biggest pancake on the bottom and the smallest pancake on top [with all the burnt sides down] if they start in an arbitrary disordered state, and the only thing you’re allowed to do is put a spatula somewhere in the middle, pick up the ones above it, flip them over, and put them down, as a group. Doing that repeatedly, putting a spatula in different places, you want to sort this out. So a very physical thing, that got me excited when I found out that no one knew the answer in general for how many flips it takes to sort this thing.

Here is help us visualize this problem is our friendly neighborhood Godzilla. He’s going to use oreos with tops removed to simulate the pancakes.

With only one “pancake”, if it starts like this

the “burnt” side is already at the bottom, so it needs 0 flips to get into the proper position.

If, instead, the pancake starts “burnt” side up, it needs one flip:

(Don’t you think that Godzilla looks a little bit like that guy Craig from Hell’s Kitchen?) As the Big G has just demonstrated, if you have just ONE burnt pancake then it could take as many as, well, 1 flip to orient it correctly. That’s where the 1 in the sequence 1, 4, 6, 8, … comes from.

Now let’s look at what happens with two burnt pancakes. We want to end up with the larger pancake on the bottom, and all the burnt sides down like this:

But what will happen if the pancakes start off in a different configuration? How many flips have to be done? It turns out that it could be as many as 4 flips:

Suppose your pancakes start off in this pile: , with the burnt parts on top. The first thing Godzilla does is to put the spatula on the bottom and flip the pile over.

Now the pancakes have the burnt side down, but the smaller one is on the bottom. The big top pancake will have to be flipped:

(Godzilla’s being a little sloppy here: he should only be picking up the top pancake.) After this maneuver the burnt parts are on the “outside” but big pancake is still on top. The entire stack needs to be flipped to get the little pancake back on top:

Now the little pancake is on the top and the burnt parts are on the “outside”, so the top pancake must be flipped:

And now voilà, the pancakes are in the right order!

See how happy Godzilla is! He knows he gets to eat these oreos when all is said and done.

With a different starting configuration (there are 2!·2²=8 ways they initially could be piled up, with the smaller pancake on the top or the bottom, and the various burnt sides up or down), it turns out that it will take at most 4 flips to get them in the correct order. That’s where the 4 comes from in 1, 4, 6, 8, ….

What happens if you start with three pancakes of different sizes? The desired ending configuration is this:

There are 3!·2³=48 different ways the pancakes could start out. Some of them could be turned into the proper configuration after just one flip:

but other configurations require more. This one, for example:

The cookies are in the right order, but it just takes a lot of maneuvering to get the burnt parts on the bottom instead of the top: 6 flips. That’s the most it would take no matter how the pancakes started out.

So for one pancake it could take as many as 1 flip, for two pancakes it takes up to 4 flips, for three pancakes up to 6 flips, for four pancakes up to 8 flips, for five pancakes up to 10 flips, for six pancakes up to 12 flips, and for seven pancakes up to 14 flips.

Then for eight pancakes, it only takes up to 15 flips. And for nine pancakes 17 flips, then for ten pancakes it goes up to 18 flips (according to the Online Encylopedia of Integer Sequences). But by 11 pancakes there are over 81 billion different initial configurations, so checking by hand to find the smallest number of flips for each configuration is tough. Fortunately, as described in this earlier post, we have E. Coli to help us figure it out. [They give the E. Coli a configuration, let them do a specific number of flips, and any E. Coli that get the virtual pancakes in the right order become resistant to the antibiotic tetracycline in honor of their good effort. Then the scientists add some tetracycline and if any of the E. Coli survive, they know that the pancakes could be put in order after that particular number of flips. The animation E. Hop gives the whole scoop.]

Meanwhile, Godzilla is going to take a little break. Bon appetit!

Tags: burnt pancake problem, David X Cohen, pattern