|
%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
| 