No Flipping without End

The applet below simulates a stack of pancakes ordered by the size, with #1 being the smallest. A flip consists in choosing an integer and turning upside down that number of top pancakes. In the applet, the number is chosen for you. This is the number of the top pancake. Every time you click the "One flip" button. The applet turns around the number of pancakes equal to the number of the top one, counting from the top.

You are to prove that the process eventually terminates and explain why.

What if applet does not run?


|Contact| |Front page| |Contents| |Algebra| |Activities| |Eye opener| |Store|

Copyright © 1996-2017 Alexander Bogomolny

Regardless of how big the total number N of pancakes is, there is only a finite number of possible stacks. Every stack corresponds to a permutation of the set {1, 2, ..., N}. There are N! of them - a big but a finite number.

Observe that when the pancake #M is on top, it goes directly to its proper location (which is #M from the top.)

Now, assuming to the contrary, namely, that the process never stops, we are bound to consider as a fact that sooner or later the stack configurations of pancakes began repeating. Choose any configuration, its first repetition, and the sequence of configurations in-between. In this sequence, find the pancake with the largest number written on it that has changed its location between one configuration to the other. Having this number leads to a contradiction. Indeed, once in place, this pancake could not possibly move again. However, if the sequence of configurations to be repeated, the next time around in order to get to its own spot in the configuration, that pancake would have to be located at the top of the stack. This could be only possible if it was a part of a larger stack that had been turned upside down - in contradiction with the assumption that it carries the largest number ever turned in the sequence.

Thus the sequence of configurations cannot start repeating itself. But there is only a finite number of them. This means that, even if it goes through all possible configurations, the stack should end up with the pancakes #1 on top. And this will be really the end of the process because, from that moment on, that pancake will be the only one that could be turned upside down.

|Contact| |Front page| |Contents| |Algebra| |Activities| |Eye opener| |Store|

Copyright © 1996-2017 Alexander Bogomolny


Search by google: