# Loop or Halt: What Is This About?

A Mathematical Droodle.

What if applet does not run? |

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

Copyright © 1996-2018 Alexander BogomolnyStarting 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 L^{th} 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 L^{th} 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

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

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

Copyright © 1996-2018 Alexander Bogomolny69100920