102 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS
1 2 3 4 5 6
12
1
2
3
4
5
Consequently, the entire large rectangle is not homogeneous, contradicting the as-
sumption that a tiling existed. So the tiling is impossible. _Monovariants
A monovariant is a quantity that mayor may not change at each step of a problem, but
when it does change, it does so monotonically (in only one direction). Another term
used for monovariant is semi-invariant. Monovariants are often used in the analysis
of evolving systems, to show that certain final configurations must occur, and/or to
determine the duration of the system. Many monovariant arguments also make use
of the extreme principle (at least the well-ordering principle). Here is a very simple
example.
Example 3.4.14 In an elimination-style tournament of a two-person game (for exam
ple, chess or judo), once you lose, you are out, and the tournament proceeds until only
one person is left. Find a formula for the number of games that must be played in an
elimination-style tournament starting with n contestants.Solution: The number of people who are left in the tournament is clearly a mono
variant over time. This number decreases by one each time a game is concluded.
Hence if we start with n people, the tournament must end after exactly n - 1 games! _Here is a more subtle problem, one that shows the importance of combining the
extreme principle with a monovariant.
Example 3.4. 15 The n cards of a deck (where n is an arbitrary positive integer) are
labeled 1,2, ... , n. Starting with the deck in any order, repeat the following operation:
if the card on top is labeled k, reverse the order of the first k cards. Prove that eventually
the first card will be 1 (so no further changes occur).Investigation: For example, if n = 6 and the starting sequence was 362 1 54, the
cards evolve as follows:
362154 ---+ 263154 ---+ 623154 ---+ 45 1 326 ---+ 315426
---+ 513426 ---+ 243156 ---+ 423156 ---+ 132456.It would be nice if the number of the card in the 1 st place decreased monoton
ically, but it didn't (the sequence was 3, 2, 6, 4,3,5,2 ,4, O. Nevertheless, it is worth
thinking about this sequence. We shall make use of a very simple, but important,
general principle: