Exact Number of Flips Required to Sort a Burnt Stack of Pancakes

Abstract

In this work, we consider the burnt pancake problem, which is a well-studied problem going back to a work of Gates and Papadimitriou from 1979. The problem is to sort a stack of n one-sided burnt pancakes of different sizes, by a sequence of flips of the top pancakes, such that at the end of the flipping sequence the pancakes have increasing size and the burnt sides of all pancakes are face-down. The pancakes are denoted by 1, 2, ..., n, and a number is multiplied by -1, if the corresponding pancake has burnt side face-up. Let T(n) be the minimum number of flips to sort a special stack of n pancakes, namely [-1,-2,...,-n]. This instance has strong relevance because of its easy structure and as it has been shown to be a worst-case instance for several small n. Heydari and Sudborough gave in 1997 the currently best upper bound of T(n), namely (3n+3)/2 for n = 3 mod 4, which later has been shown to be exact by a work of Cibulka from 2011. Except these two works, no progress regarding lower and upper bounds has been made until now. In our work, we present that (3n+3)/2 is also an upper bound of T(n) for n = 1 mod 4, which again matches the lower bound of Cibulka in 2011 and thus is exact. Furthermore, we show that our construction approach for n = 1 mod 4 and the one of Heydari and Sudborough for n = 3 mod 4 cannot be applied for even n. However, as there might be different construction approaches, the case of even n remains an open problem, where two possible values for T(n) are possible, namely (3/2)n + 1 or (3/2)n + 2. Finally, we found two values, namely n = 24, n = 26, where the lower bound is attained.