3.4 INVARIANTS^103If there are only finitely many states as something evolves, either a state
will repeat, or the evolution will eventually halt.
In our case, either the sequence of 1st-place numbers repeats (since there are only
finitely many), or eventually the 1st-place number will be I (and then the evolution
halts). We would like to prove the latter. How do we exclude the possibility of repeats?
After all, in our example, there were plenty of repeats!
Once again, the extreme principle saves the day. Since there are only finitely
many possibilities as a sequence evolves, there exists a largest 1st-place value that
ever occurs, which we will call LI (in the example above, LI = 6). So, at some point in
the evolution of the sequence, the 1st-place number is LI, and thereafter, no 1st-place
number is ever larger than L 1 • What happens immediately after LI occurs in the 1st
place? We reverse the first LI cards, so LI appears in the LI th place. We know that
the 1st-place card can never be larger than LI, but can it ever again equal LI? The
answer is no; as long as the I st place value is less than LI , the reversals will never
touch the card in the L I th place. We will never reverse more than the first LI cards
(by the maximality of LI), so the only way to get the card numbered LI to move at all
would be if we reversed exactly LI places. But that would mean that the 1st-place and
LI th-place cards both had the value LI, which is impossible.
That was the crux move. We now look at all the 1st-place values that occur after
LI appeared in the I st place. These must be strictly less than LI. Call the maximum of
these values L 2. After L 2 appears in 1st place, all subsequent 1st-place values will be
strictly less than L 2 by exactly the same argument as before.
Thus we can define a strictly decreasing sequence of maximum I st-place values.
Eventually, this sequence must hit I, and we are done!
The above was a little vague. It is instructive to give a more formal argument,
especially to illustrate careful use of subscripts and notation.
Formal Solution: Let fi be the value of the I st card after i steps, i = 1,2, .... We
wish to show that fm = I for some m (and consequently, fn = I for all n 2: m). Since
I :::; f; :::; n, the number
LI := max{fi : i 2: I}exists. Also define
tl := min{t : It = LI};i.e., tl is the first step at which the I st card is equal to LI. In the example above, LI = 6
and tl = 3.
We claim that if t > tl, then It < LI. To see this, notice that ft cannot be greater
than LI, by the definition of LI. To see that It cannot equal LI, we argue by contra
diction. Let t be the first step after tl such that It = LI. At step tl, the first LI cards
were reversed, placing the value LI at the LI th place. For all steps s after tl and before
t, we have fs < LI, which means that the card with the value LI at the LI th place was
not moved. Hence at step t, it is impossible for It = LI , since that means that the 1st
and Lith are the same (unless LI = I, in which case we are done). This contradiction
establishes the claim.