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

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