Loop or Halt: What Is This About?
A Mathematical Droodle.


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Loop or Halt


What if applet does not run?

Explanation

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

Copyright © 1996-2017 Alexander Bogomolny

Starting with a permutation of the set of the first N integers 1, 2, 3, ..., N, repeat the following operation: if the first number is k, reverse the order of the first k numbers. Prove that eventually the number 1 will become the first, at which time the iterations will halt.

For example, starting with 362154 we reverse the first 3 cards to obtain 263154, then reverse the first 2, and so on:

362154
263154
623154
451326
315426
513426
243156
423156
132456

There is a general principle that we shall apply to solving the problem:

Any process with a finite number of possible states either halts (terminates) or enters a loop (wherein a sequence of states is repeated indefinitely.)

We shall apply this principle to the series of first place numbers, which in our example are

3, 2, 6, 4, 3, 5, 2, 4, 1

Note that, although there are some repetitions, the process does not enter a loop and eventually terminates. We wish to prove that this is true in general.

If the original permutation has N as the last number, N will never turn up in the first place. However, since the total number of the possibilities is finite, there is always the largest number (different for different starting permutations) that ever occurs at the first place during the iterations. Let this number be L. Thus at some point, L will be the first number in the sequence. At this time L terms will be reversed. In particular the number L itself will be moved to the Lth place. Thereafter, L could not possibly return to the beginning of the sequence, because for this to happen the first number must be L, to begin with, or a larger number beforehand that would move L from its Lth place. But since L denotes the largest number to ever occur in the first place, the latter event could not possibly happen. Thus L may come to the first place only once.

Let's apply the foregoing argument to the sequence obtained immediately after that happens.

The new largest number that ever occurs in the first place is necessarily less than L and also occurs only once. In this manner we obtain a strictly decreasing sequence of positive integers, which can't be infinitely long. But the only number it may terminate with is 1, which completes the proof.

References

  1. P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999, Example 3.4.15 (pp. 112-114)

Related material
Read more...

  • 3-Term Arithmetic Progression
  • Aliquot game (An Interactive Gizmo)
  • Euclid's Game (An Interactive Gizmo)
  • Euclid's Game on a Square Grid
  • Sums and Products
  • Sums and Products, a Generalization
  • Sums, Products, and 1-1 Functions
  • Zeros and Nines
  • A Candy Game: Integer Iterations
  • A Candy Game (Change Discharged)
  • Heads and Tails
  • Breaking Chocolate Bars (An Interactive Gizmo)
  • |Activities| |Contact| |Front page| |Contents| |Algebra| |Store|

    Copyright © 1996-2017 Alexander Bogomolny

     62040971

    Search by google: