IBM Ponder This #006 · October 1998

There are $N$ pancakes of distinct sizes. The aim is to put them in the order

$$1,2,\dots ,N,$$

with the smallest pancake on top. The only permitted operation is to choose $1\le k\le N$ and reverse the top $k$ pancakes:

$$(a_1,a_2,\dots ,a_k,\dots )⟶(a_k,a_{k-1},\dots ,a_1,\dots ).$$

For a permutation $p$, let $f(N,p)$ be the fewest flips needed to sort it, and define

$$g(N)=\underset{p\in S_N}{max}f(N,p).$$

How does $g(N)$ grow? IBM gives $g(5)=5$ as a starting point.

Solution

Best opened after a real attempt

Solution

To be added.