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

by

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!·22=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!·23=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: , ,

13 Responses to “4, 6, 8, 10, 12, 14,….What comes next?”

  1. Denise Says:

    This was fun! I hadn’t read about this puzzle before. I’ll have to find some scratch paper and see if I can figure out all those flips. If I make it all the way to 15, will Godzilla share his cookies?

  2. Logic Nest · Carnival of Mathematics #37 Says:

    […] Ξ_Heather wants us to think about Burnt Pancakes and Godzilla at her article 4, 6, 8, 10, 12, 14,?.What comes next? posted at 360. As she explains, “the Burnt Pancake problem involves pancakes of different […]

  3. Ξ Says:

    Sure thing Denise! I got as far as analyzing how many flips it would take for each of the 3-pancake combination (I only found two that required 6 flips) but didn’t try anything more.

    I did notice, however, that with 1, 2, or 3 pancakes, having the pancakes in order with the smallest on top and largest on the bottom, but the burnt sides UP instead of down, always provided one of the worst-case (maximum flips) scenarios, and then I noticed on the Online Encyclopedia of Integer Sequences above that that was conjectured to always give the maximum number of flips. So if you want to try, that’s how I’d suggest starting!

  4. Denise Says:

    I had guessed that myself, but I didn’t want to ask or look it up until I had tried several examples.

  5. Ξ Says:

    I thought it was interesting that it’s still a conjecture. I had thought that the Burnt Pancake Problem was still open, but if I’m reading OEIS correctly, after 10 pancakes the “at most ___ flips” goes up by 2 each time, which would make it one weird sequence (why the two spots at y to 8 pancakes and 9 to 10 pancakes flipts where it only goes up by 1 flip when another pancake is added???

  6. Joey Says:

    So, I think Godzilla Chef needs to be in every article ever published.

  7. Ξ Says:

    Thanks Joey! Chef Godzilla certainly would agree, especially if he gets to sport his new hat and eat Oreos. Of course, that would mean that his work station should be kept clean at all times, instead of magnetically attracting all groceries, mail, and cats that come into the kitchen.

  8. Two dot leader Says:

    http://xkcd.com/169/

  9. Ξ Says:

    Two dot — my apologies if the title was misleading in a frustrating rather than amusing way. I find it really neat when there are sequences that occur “naturally” somehow and appear to follow one pattern but then suddenly switch gears and do something different! (I’ve posted about this before under “Patterns that Fail”). The next number should be 16, and in a fundamental way I don’t understand why it only takes 15 flips at most for 8 pancakes.

  10. The Carnival of Mathematics « problemas | teoremas Says:

    […] Ξ_Heather wants us to think about Burnt Pancakes and Godzilla at her article 4, 6, 8, 10, 12, 14,?.What comes next? posted at 360. As she explains, “the Burnt Pancake problem involves pancakes of different sizes, […]

  11. Hot off the Press! A History of Math resource « 360 Says:

    […] And she talked to David X. Cohen about Futurama Math in an interview that has been referenced on this blog.    So the mere fact that I knew her name so well that I thought we must be best buds is a […]

  12. Godzilla makes a hexaflexagon « 360 Says:

    […] makes a hexaflexagon By Ξ When Godzilla isn’t trampling buildings, flipping pancakes, or making cookies, he likes to engage in the fiber […]

  13. Alte bloguri de matematica « Blog de matematica Says:

    […] threesixty360.wordpress.com (aici am gasit problema prajiturilor arse ) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: