## October 1998

<<September
**October**
November>>

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 **k**th 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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

*If you have any problems you think we might enjoy, please send them in. All replies should be sent to:* ponder@il.ibm.com

**Challenge:**
10/01/98 @ 12:00 AM EST

**Solution:**
11/01/98 @ 12:00 AM EST

**List Updated:**
11/15/01 @ 10:00 AM EST

### People who answered correctly:

**Attention:** If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.