8
$\begingroup$

You are cooking pancakes for your lovely wife. You want to sort the pancakes such that they increase in diameter as you move from the top to the bottom of the stack. The only operation you can perform on the stack is to insert your spatula into the stack and flip over (that is, reverse the order of) the top portion of the stack. Your stack from top to bottom has pancakes with diameters 4, 6, 2, 5, 1 and 3. What is the fewest number of flips you need to sort the stack?

$\endgroup$
  • 1
    $\begingroup$ Fewest number of flips or fewest number of pancakes flipped? $\endgroup$ – JMP Mar 16 at 8:24
  • 1
    $\begingroup$ Fewest number of Flips $\endgroup$ – Dmitry Kamenetsky Mar 16 at 8:27
  • $\begingroup$ There's an assumption you only have one stack (ie one plate), right ? $\endgroup$ – Criggie Mar 16 at 18:26
  • 1
    $\begingroup$ @Criggie yes one plate. Multiple plates would be quite interesting too. Starting to look like Towers of Hanoi... $\endgroup$ – Dmitry Kamenetsky Mar 17 at 1:30
11
$\begingroup$

It can be done in

7

flips.

4 6 2 5 1 3 (2)
6 4 2 5 1 3 (6)
3 1 5 2 4 6 (4)
2 5 1 3 4 6 (3)
1 5 2 3 4 6 (2)
5 1 2 3 4 6 (5)
4 3 2 1 5 6 (4)
1 2 3 4 5 6

In general case of this puzzle is an open problem called the pancake sorting problem. It is known that with $n$ pancakes the worst case takes somewhere between $\frac{15}{14}n$ and $\frac{18}{11}n$ flips. It can of course easily be solved in no more than $2(n-1)$ flips by repeatedly flipping the largest unsolved pancake to the top and then flipping it to its correct position.

For small numbers such as $n=6$ it is easy to calculate completely, and the starting position in this puzzle is one of the two worst permutations to solve (the other being its inverse permutation).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Very well done! Yes this is a well known open problem, but I haven't seen it here, so I thought I would share. $\endgroup$ – Dmitry Kamenetsky Mar 17 at 1:31
2
$\begingroup$

I can do it in

8 flips

Here is the stack, bottom to top, after each of the flips --

3 1 5 2 6 4
3 1 5 2 4 6
6 4 2 5 1 3
6 4 2 3 1 5
6 5 1 3 2 4
6 5 4 2 3 1
6 5 4 2 1 3
6 5 4 3 1 2
6 5 4 3 2 1

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.