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.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

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 {1, 2,..., n}. The allowed moves are represented by permutations

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 {1, 2, ..., n} starting with the index i. The fact that the puzzle is solvable for any permutation from S_n implies that the set {M₁, M₂, ..., M_n-1} generates S_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) that exchanges elements i and (i+1) can be written as

(i i+1) = M_i+1M_iM_i+1M_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 n) = M_n-1.) It's an interesting exercise to find such representation for a general transposition (i j).

There is another interesting question. What if, on any move, we were only allowed to flip a fixed number k of elements? For k = 2, the only allowed moves would be (1 2), (2 3), ..., (n-1 n). For k = 3, the set of moves would consist of (1 3), (2 4), ..., (n-2 n). For k = 4, we would have only {4 3 2 1}, {5 4 3 2}, ..., {n n-1 n-2 n-3} (we might also add {n n-1 n-2) and (n n-1),(n n-1), should this be necessary.)

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.

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 2n - 3 moves.

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 in  last 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
    https://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
    https://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?

73198011