I'm Pancake!

Math problem of the day: The Pancake Problem - What is the maximum number of flips required to reorder a stack of n pancakes so they are all ordered by size - biggest at the bottom, smallest on top.

Nicely explained in this little gem of a popular math article by Simon Singh: Flipping pancakes with mathematics.

Pinkie Pie enjoys a challenging math problem.

Twilight decides to sleep on the problem.

Comments

[Georg]

With Pinkie, the answer is 'One.' She just flips the whole stack up in the air, and they come down sorted

[ShadowStorm7]

The answer is 1234567891011121314151617181920

[Booster Spice]

Wouldnt it be the Minimum number, as teh maximum number is infinite, you just keep reversing the order each end before completion?

I would also hope its more to do with the classic Quicksort, a binary tree division method, as even bubblesort is faster than Tower Of Pancakes?

Or you can use Pidgeon sort, in which case its 0.

Eat the biggest pancake first and select your way through the pile. Therefore, since you have integrated the sorting and eating, the sort takes zero time?

[FanOfMostEverything]

I'm pretty sure my answer to this problem would be zero, since the pancakes would be gone by the time someone finished positing it.

[horizon]

Clearly Twilight is working on an even harder variant, the Pancake Problem With Chocolate Chips. Namely, if you have a chip-applying machine which can be arbitrarily triggered to embed chips into your pancake stack, and a stacked pancake p receives chips if and only if there are no pancakes larger than p on the stack above p, how many flips are necessary to add chips to every pancake?

[Pineta]

3743375

Wouldnt it be the Minimum number, as teh maximum number is infinite, you just keep reversing the order each end before completion?

To clarify, it is the maximum value of the minimum number of flips required for all possible orderings (if that makes sense).
If the stack is already ordered then it requires 0 flips, but we are interested in the number of flips required in worse case scenario when the pancakes are as disordered as possible.
i.guim.co.uk/img/static/sys-images/Guardian/Pix/pictures/2013/11/8/1383936625188/pancake-flipping-001.jpg?w=620&q=85&auto=format&sharp=10&s=8d29aadbdb4de9ad2de2c264fc3ad684

[Waterpear]

I'm surprised you didn't mention the coolest part of that Wikipedia article:

In a more difficult variation called the burnt pancake problem, the bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down. In 2008, a group of undergraduates built a bacterial computer that can solve a simple example of the burnt pancake problem by programming E. coli to flip segments of DNA which are analogous to burnt pancakes. DNA has an orientation (5' and 3') and an order (promoter before coding). Even though the processing power expressed by DNA flips is low, the high number of bacteria in a culture provides a large parallel computing platform. The bacteria report when they have solved the problem by becoming antibiotic resistant.[6]

Then again, that'd be hard to represent with ponies.

[the dobermans]

Next time, Pinkie tackles P(ancake) vs. NP(ancake).

[BlazzingInferno]

3743364
And land in her mouth, of course

[michaelb958]

3743574 Surely that wouldn't alter the problem at all? The trivial solution appears to be to treat the problem as unmodified, then (once the pancakes are all stacked in size order) apply chocolate chips. Since all pancakes p are above all pancakes larger than p, all pancakes would receive chips.

An alteration that would make the exercise much more fun would be "Only the pancake on the top of the stack receives chocolate chips." For extra credit, apply chips only to the unburnt side!

[horizon]

3744872
Eenope! Different problem!

Consider the stack of pancakes: {2 4 3 1}. (I'm using this notation: 1 is the smallest pancake and 4 is the largest. Read left-to-right order as going from the top down; so that's a pancake stack with 2 on top and 1 on the bottom. A vertical bar | is where the spatula is inserted to progress your stack to the next state.)

With the traditional pancake problem, the most efficient sequence takes three flips: {2 4 3 | 1} -> {3 4 | 2 1} -> {4 3 2 1 | } -> {1 2 3 4}.

With the PPWCC variant, all you need to do is chip every pancake. Begin by chipping: {c2 c4 3 1}. Then simply flip the stack {c2 c4 3 1 |} -> {1 3 4c 2c} and chip again. Voila, finished in one flip.

More formally: the maximum necessary flips for a PPWCC stack of size n has a trivial upper bound of (n-1), because that's all it takes to bring a different pancake to the top of the stack with each flip. [1] (I'm sure the real maximum value is lower, possibly significantly lower.) But if you look up the original Pancake Problem, its maximum necessary flips has a lower bound of (15/14 * n). (n-1) < (15/14*n) so the solution for both problems cannot be the same.

... now I kind of wish I was still a mathematician, because I'm actually curious how much basis my joke actually has (of PPWCC being harder), but I can't afford the leisure time of researching it in hopes of a publishable paper in a field I formally dropped out of decades ago. I can't imagine it's literally harder than PP, but it's also a new variant that hasn't been researched yet, and (assuming that the solution isn't trivial), it might be equally complex. My gut tells me that the actual value is closer to n/2, but in mathematics gut feelings have a way of being interestingly wrong.

--
[1] By the way, that's the solution to the problem you propose: if only the top pancake is chipped, the solution is always exactly (n-1), because you simply follow this pseudocode: {chip top pancake j; for k = 1..n (next if k=j; flip from underneath pancake k; chip) }. This is trivially the most efficient algorithm because it's impossible to chip more than one pancake at a time and it's impossible to put more than one new pancake on top with each flip.

[michaelb958]

3744906 Oh, I see. I misinterpreted the pancake-with-chips problem as requiring ordering (as in the original problem) as well as adding chocolate chips.