2022/11/26 by Hunter, Zach
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2211.14678
The "pancake problem" asks how many prefix reversals are sufficient to sort any permutation π∈ Sk to the identity. We write f(k) to denote this quantity. The best known bounds are that (15)/(14)k -O(1) ≤ f(k)≤ (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 π∈ Sk. We observe that (15)/(14)k -O(1)≤ h(k) still holds, and give a human proof that h(k) ≤ (3)/(2)k +O(1). The constant "(3)/(2)" is a natural barrier for the pancake problem and this variant, hence new techniques will be required to do better.