Abstrakt
We are given a stack of pancakes of different sizes and the only allowed operation is to take several pancakes from the top and flip them. The unburnt version requires the pancakes to be sorted by their sizes at the end, while in the burnt version they additionally need to be oriented burnt-side down.
We study the largest value of the number of flips needed to sort a stack of n pancakes, both in the unburnt version (f(n)) and in the burnt version (g(n)). We present exact values of f(n) up to n=19 and of g(n) up to n=17 and disprove a conjecture of Cohen and Blum by showing that the burnt stack -I(15) is not the hardest to sort for n = 15.
We also show that sorting a random stack of n unburnt pancakes can be done with at most 17n/12 + O(1) flips on average. The average number of flips of the optimal algorithm for sorting stacks of n burnt pancakes is shown to be between n + Omega(n/log n) and 7n/4 + O(1).
We slightly increase the lower bound on g(n) to (3n + 3)/2.