Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Terms of use
Privacy Policy

More Mathematics
CTK Exchange

Games to Relax
Guest book
Recommend this site

Sites for teachers
Sites for parents

Manifesto: what CTK is about Buying a book is a commitment to learning Things you can find on CTK Email to Cut The Knot Recommend this page

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.)

<hr> <h3> This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet. </h3> <hr>

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

Mi = {1 . (i-1) n (n-1) (n-2) . (i+1) i},

where Mi amounts to the flipping of the tail of the set {1,2,.,n} starting with the index i. The fact that the puzzle is solvable for any permutation from Sn implies that the set {M1,M2,.,Mn-1} generates Sn. (Why has Mn been omitted?). In particular, any transposition can be expressed as a product of Mi's. For example, the transposition (i i+1) that exchanges elements i and (i+1) can be written as

(i i+1) = Mi+1MiMi+1Mi+2,

where, by convention, we first flip Mi+1, then Mi, and so on, left to right. (When indices get out of scope simpler formulas apply. For example, (n-1 n) = Mn-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



Search:
Keywords: