A new upper bound to (a variant of) the pancake problem

Abstract

The "pancake problem" asks how many prefix reversals are sufficient to sort any permutation $\pi \in {\mathcal{S}}_k$ to the identity. We write $f(k)$ to denote this quantity. The best known bounds are that $\frac{15}{14}k-O(1)\le f(k)\le \frac{18}{11}k+O(1)$. The proof of the upper bound is computer-assisted, and considers thousands of cases. We consider $h(k)$, how many prefix and suffix reversals are sufficient to sort any $\pi \in {\mathcal{S}}_k$. We observe that $\frac{15}{14}k-O(1)\le h(k)$ still holds, and give a human proof that $h(k)\le \frac{3}{2}k+O(1)$. The constant "$\frac{3}{2}$" is a natural barrier for the pancake problem and this variant, hence new techniques will be required to do better.

9 pages, comments welcome!