# Flipping pancakes

Here is a simple puzzle. There is a number of pancakes all of different sizes. Pancakes are stacked on top of each other. You are allowed to slip a flipper under one of the pancakes and flip over the whole stack above the flipper. The purpose is to arrange pancakes according to their size with the biggest at the bottom. In the simulation below you should just click on the pancake under which, in the real world, you would slip a flipper.

Actually, a physical, mundane activity like flipping pancakes may at best serve only as a starting point for a puzzle. Other moves could be envisaged that would require very special training to carry out. For example, we may allow to only flip "end points" of the stack. This is controlled with the "Scarce" checkbox. In a second modification, we fix the interval of the stack to which a move applies. It may apply to intervals of length 2,3,4, etc. (with adjustments towards the top of the stack.)

What if applet does not run? |

When you press "Reset" or select another number of pancakes, I reshuffle the original (and final) configuration. To reshuffle, I repeatedly pick a random pancake and flip. Therefore, every puzzle you are presented with is solvable: just follow the reshuffle flips in reverse order. However, you may be interested in proving that, when moves involve flips "up to the top", the puzzle is solvable for *every* permutation
of pancakes. There is a simple constructive proof that offers a strategy that necessarily leads to a solution.

We may draw several conclusions. But, instead of dealing with simulated pancakes, let's agree to permute (flip) elements of the set

M_{i} = {1 ... (i-1) n (n-1) (n-2) ... (i+1) i},

where M_{i} amounts to the flipping of the tail of the set _{n} implies that the set _{1}, M_{2}, ..., M_{n-1}}_{n}. (Why has M_{n} been omitted?). In particular, any transposition can be expressed as a product of M_{i}'s. For example, the transposition

(i i+1) = M_{i+1}M_{i}M_{i+1}M_{i+2},

where, by convention, we first flip M_{i+1}, then M_{i}, and so on, left to right. (When indices get out of scope simpler formulas apply. For example, _{n-1}.)

There is another interesting question. What if, on any move, we were only allowed to flip a fixed number k of elements? For

The assertion for k = 3 is obviously wrong. Right? What about other k's?

A few words of the "scarce" variant of the puzzle. Surprisingly, the constructive strategy that worked before works now as well. It then follows, that any permutation can be represented as a product of transpositions all of which transpose a fixed index ("top" index in this case.) This result has also been established quite directly as Theorem 1 in a discussion on transpositions.

|Contact| |Front page| |Contents| |Algebra| |Eye opener| |Store|

Copyright © 1996-2017 Alexander Bogomolny

### Proof

The algorithm is as follows. Slide the flipper under the largest pancake that is out of order. Flip, putting this pancake at the top. Now slide the flipper just above the smallest pancake that is in its proper place. Flip, and now the largest pancake that was out of order is now in order.

Continuing in this manner you clearly will arrange all pancakes in the correct order. See if you can use induction to make this argument rigorous.

With this strategy the puzzle is solved in at most

From a post by Bob Harris (Lawrenceville, GA) at the alt.math.recreational newsgroup I learned that the problem has been discussed in October 98 at the Ponder This site. Following is his message:

Subject: | Re: Pancakes |
---|---|

Date: | Fri, 22 Jun 2001 07:18:52 -0400 |

From: | Bob Harris |

Newsgroups: | alt.math.recreational |

Kevin T. Crowley wrote: > "The chef in our place is sloppy, and when he prepares a stack of pancakes > they come out all different sizes. ... This was discussed inlast year. The text that I saved shows an original post by "M Killianey" on April/25/2000 9:04 PM titled "Pancake puzzle". You folks that are better with usenet than I am can probably find that whole thread. At the time, that thread led me to an IBM puzzle site. I've found a saved link to it, WHICH NO LONGER WORKS, at http://www.research.ibm.com/features/pancake/solution.html The title of the page at that time was "October 98 Ponder This". With some more digging I found http://www.research.ibm.com/ponder/ which gives links to the monthly puzzles. Unfortunately, it appears that they've tossed all the puzzles prior to '99. Oh wait. I saved some of the text from that web page. I've appended it below. Bob Harris Lawrenceville, GA ========== Pete's Pancake Pandemonium You must help Pete the pancake chef! He's desperately trying to sort his pancakes by size. How many flips will it take? There is a stack of N pancakes -- each one a different size -- on top of the griddle. Your goal is to get the pancakes in a stack arranged by size, with the largest pancake on the bottom, smallest one on top. You must accomplish this by flipping the pancakes a limited number of times. For each flip, you must (on Pete's behalf): Choose a number k between 1 and N. Pick a pancake in the kth position (counting from the topmost pancake) and insert your spatula under it (between the pancakes in position k and (k+1). Then flip the pancakes on your spatula, reversing the order. Example: N=5 (Numbers on the pancakes represent the size of the pancake, not its position.) The smallest pancake is labeled "1": Initial position: Top 1 3 5 2 4 Griddle First move (k=3) Yields: Top 5 3 1 2 4 Griddle Second move (k=5) Yields: Top 4 2 1 3 5 Griddle Third move (k=4) Yields: Top 3 1 2 4 5 Griddle Fourth move (k=3) Yields: Top 2 1 3 4 5 Griddle Fifth move (k=2) Yields: Top 1 2 3 4 5 Griddle We used 5 moves to sort the stack. Here's what we want you to tell us: * For a given N, what is the least number of flips with which you can guarantee that you will correctly sort the stack? * For every N, for every initial position, can it be done in N flips? * How many flips could be required for a given N and the worst possible initial position? In other words, if we consider N to be fixed, for each initial permutation, there is some minimum number of flips that works. Find the maximum of these minima as you vary the permutations, i.e. find a hardest permutation. E.g. if N=5, the permutation (Top 2,1,3,4,5 Griddle) would require only one flip, although you could take a roundabout path and take 13 flips. The minimum for this permutation is 1. The minimum for the permutation (Top 1 3 5 2 4 Griddle) is 5 flips as shown. It turns out that any other permutation can also be done in 5 flips. So 5 is the answer we're looking for here. Or, to put this in simple mathematical terms: For N=number of pancakes, p=permutation Let f(N,p) be the minimum number of flips when faced with initial permutation p; let g(N) be the maximum of f(N,p) over choices of p. Find g (N). FYI: Although this problem may appear simple at first, the solution is actually fairly complex. ========== A Solution (?) for Chef Pete We don't know the complete answer to this. Let f(N) be the least number of flips guaranteed to bring any initial permutation of N pancakes into the proper order. We will see below that f(N) is between N and 2N-3. If N is at least 4 we know that f(N) is at least N. To see this, count the number of instances where pancakes k and k+1 (or pancake N and the griddle) are adjacent; call them "good pairs". Start with a permutation like (1,3,5,2,4) (if N is odd) or (2,4,6,1,3,5) (if N is even); such a permutation has no good pairs. Each flip can bring only one pair of pancakes into contact (or bring the largest pancake into contact with the griddle), so that the number of good pairs increases by at most 1. Since we want to end up with N good pairs (1,2), (2,3), ..., (N-1,N) and (N,griddle), it must require at least N flips to do so. But some permutations can require more than N flips. The permutation 536142 -> 123456 requires at least 7 flips, showing that f(6) is at least 7. (In fact f(6)=7.) For an upper bound of 2N-3, follow this procedure. Find the largest pancake and with one flip bring it to the top. Then flip the whole stack, putting that largest pancake onto the griddle. Now sort the remaining N -1 pancakes. It took us two flips to put pancake N into its proper position, another two to put N-1 into position, and so on, until we have put pancake 3 into position (using 2 N -4 flips so far). We are left with two pancakes, which can be sorted with at most one flip, bringing our total to 2N-3 at most. Gates and Papadimitriou (Discrete Math 27 pp. 47-57, 1979) have shown tighter bounds: (17N /16) < f(N) < (5 N /3). This problem originally appeared in the American Mathematical Monthly in 1975, submitted under the pseudonym "Harry Dweighter". The most recent work on the subject appears to be "On the Diameter of the Pancake Network," by M. Heydari and I. H. Sudborough, Journal of Algorithms, 25 (1997), pp. 67-94. These authors obtain a better lower bound (15N/14), and also consider the problem of burnt pancakes, where each pancake must have its lighter side facing up. ========== From: gwoegi@my-deja.com Organization: Deja.com - Before you buy. Newsgroups: Date: April/27/2000 8:35 AM Subject: Re: Pancake puzzle Before Bill Gates decided to become the richest man on earth, he was doing research on the fundamentals of algorithms. He only published a single paper, and that's on this pancake sorting problem: W.H. Gates and C. Papadimitriou, Bounds for sorting by prefix reversal. Discrete Mathematics 27 (1979), pp 47-57. They give an algorithm that sorts n pancakes with roughly 5n/3 operations. -Gerhard

This activity of flipping pancakes leads to an additional problem. Assume that the pancakes are (ordered and) numbered according to their size with the smallest being #1. Assume that the number of pancakes to be turned upside down is not arbitrary but is the one that happens to be at the top. Will the process ever end?

|Contact| |Front page| |Contents| |Eye opener| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

61257168 |