Animation scientifique
Date : 16 juin 2026 11:00 - Salle :Salle A104
How long will I wait for my pancakes? The conjectured hardest burnt pancake stack meets Cibulka's lower boundNacim Oijid - Umeå University Groupe de travail : ALCOLOCO |
For the buffet, the waiter of a restaurant gets a large stack of pancakes from the overworked cook. As expected under such harsh work conditions, one side is burnt, and as the level of batter decreases, the pancakes became smaller and smaller. Hence, the waiter ends up with a stack of one-sided burnt pancakes sorted by size, with the larger at the bottom and burnt side up. However, the waiter cannot serve them this way. He needs to turn all the burnt sides down, without changing the order. Having only a spatula, he can only perform flips to the top of the stack. How can he perform this transformation in a minimum number of flips?
The burnt pancake problem, introduced by Gates and Papadimitriou (1979), asks for the min imum number of prefix reversals (flips) needed to sort a stack of n pancakes, each burnt on one side, so that they are ordered by size with all burnt sides down. We study the specific instance -In=(-1, -2, ..., -n), conjectured to be the hardest stack to sort. Heydari and Sudborough (1997) established the upper bound (3n+3)/2 for n = 3 (mod4), later shown to match Cibulka's lower bound (2011), yielding the exact value. We extend this result to all integers n, proving that the same formula is always tight.