Flipping pancakes

Here is a simple puzzle. There is a number of pancakes all of different sizes. Pancakes are stacked on top of each other. You are allowed to slip a flipper under one of the pancakes and flip over the whole stack above the flipper. The purpose is to arrange pancakes according to their size with the biggest at the bottom. In the simulation below you should just click on the pancake under which, in the real world, you would slip a flipper.

Actually, a physical, mundane activity like flipping pancakes may at best serve only as a starting point for a puzzle. Other moves could be envisaged that would require very special training to carry out. For example, we may allow to only flip "end points" of the stack. This is controlled with the "Scarce" checkbox. In a second modification, we fix the interval of the stack to which a move applies. It may apply to intervals of length 2,3,4, etc. (with adjustments towards the top of the stack.)

When you press "Reset" or select another number of pancakes, I reshuffle the original (and final) configuration. To reshuffle, I repeatedly pick a random pancake and flip. Therefore, every puzzle you are presented with is solvable: just follow the reshuffle flips in reverse order. However, you may be interested in proving that, when moves involve flips "up to the top", the puzzle is solvable for every permutation of pancakes. There is a simple constructive proof that offers a strategy that necessarily leads to a solution.

We may draw several conclusions. But, instead of dealing with simulated pancakes, let's agree to permute (flip) elements of the set {1,2,.,n}. The allowed moves are represented by permutations

where, by convention, we first flip M_i+1, then M_i, and so on, left to right. (When indices get out of scope simpler formulas apply. For example, (n-1 n) = M_n-1.) It's an interesting exercise to find such representation for a general transposition (i j).

There is another interesting question. What if, on any move, we were only allowed to flip a fixed number k of elements? For k = 2, the only allowed moves would be (1 2), (2 3), ., (n-1 n). For k = 3, the set of moves would consist of (1 3), (2 4), ., (n-2 n). For k = 4, we would have only {4 3 2 1}, {5 4 3 2}, ., {n n-1 n-2 n-3} (we might also add {n n-1 n-2) and (n n-1), should this be necessary.)

The assertion for k = 3 is obviously wrong. Right? What about other k's?

A few words of the "scarce" variant of the puzzle. Surprisingly, the constructive strategy that worked before works now as well. It then follows, that any permutation can be represented as a product of transpositions all of which transpose a fixed index ("top" index in this case.) This result has also been established quite directly as Theorem 1 in a discussion on transpositions.

Copyright © 1996-2008 Alexander Bogomolny