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?
$\begingroup$
$\endgroup$
4
asked Mar 16, 2020 at 5:33
-
1$\begingroup$ Fewest number of flips or fewest number of pancakes flipped? $\endgroup$– JMPCommented Mar 16, 2020 at 8:24
-
1$\begingroup$ Fewest number of Flips $\endgroup$– Dmitry KamenetskyCommented Mar 16, 2020 at 8:27
-
$\begingroup$ There's an assumption you only have one stack (ie one plate), right ? $\endgroup$– CriggieCommented Mar 16, 2020 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 KamenetskyCommented Mar 17, 2020 at 1:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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).
answered Mar 16, 2020 at 7:07
-
$\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$ Commented Mar 17, 2020 at 1:31
$\begingroup$
$\endgroup$
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
