IBM Ponder This #006 · 1998 年 10 月

有 $N$ 张大小各不相同的煎饼，目标是将它们排成

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

即最小的在顶部。唯一允许的操作是选择 $1\le k\le N$，然后把最上面的 $k$ 张整体翻转：

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

对排列 $p$，令 $f(N,p)$ 为将它排序所需的最少翻转次数；再定义

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

一般的 $g(N)$ 如何增长？IBM 给出 $g(5)=5$ 作为起点。

解答

认真尝试后再打开

题解

待补充。