login
Flipping burnt pancakes. Maximum number of spatula flips to sort a stack of n pancakes of different sizes, each burnt on one side, so that the smallest ends up on top, ..., the largest at the bottom and each has its burnt side down.
3

%I #12 Jun 24 2014 01:08:33

%S 1,4,6,8,10,12,14,15,17,18,19,21

%N Flipping burnt pancakes. Maximum number of spatula flips to sort a stack of n pancakes of different sizes, each burnt on one side, so that the smallest ends up on top, ..., the largest at the bottom and each has its burnt side down.

%C In a 'spatula flip', a spatula is inserted below any pancake and all pancakes above the spatula are lifted and replaced in reverse order.

%C It is conjectured that the initial configuration in which the pancakes are in the correct order but all of the burnt sides are up is a worst case for the problem. If so, then this sequence is identical to A078942.

%D David S. Cohen and Manuel Blum, "On the problem of sorting burnt pancakes", Discrete Applied Math., 61 (1995) 105-120.

%H J. Cibulka, <a href="http://www.crm.umontreal.ca/CanaDAM2009/pdf/cibulka.pdf">Pancake Sorting</a> [From D.J. Schreffler (dj_schreffler(AT)hotmail.com), Apr 17 2010]

%H Douglas B. West, <a href="http://www.math.uiuc.edu/~west/openp/pancake.html">The Pancake Problems (1975, 1979, 1973)</a> - From _N. J. A. Sloane_, Jul 26 2012

%F a(n) >= A078942(n). a(n+1) <= a(n) + 2. 3n/2 <= a(n) <= 2n-2, where the upper bound holds for n>=10.

%Y Cf. A078942. A058986 treats the unburnt case.

%K nonn,more

%O 1,2

%A _Dean Hickerson_, Dec 18 2002

%E Two new terms added from a 2009 presentation. See the University of Montreal link below. D.J. Schreffler (dj_schreffler(AT)hotmail.com), Apr 17 2010