100 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS
Modular Arithmetic and Coloring
Parity works amazingly well, but it is rather crude. After all, we are reducing the
infinite universe of integers into a tiny world inhabited by just two entities, "even" and
"odd." Sometimes we need to explore a more sophisticated world. Examples 3.4.5 and
3.4.6 used invariants with nine and three possible values, respectively. These are both
examples of modular arithmetic, that is, the reduction of our point of view from the
infinite set of integers to the finite set of possible remainders modulo m, where m is
chosen cleverly.
For practice, here 's a quick proof of the assertion in Example 3.4.5 above. You
may wish to recall the basic properties of congruence from page 44. Without loss of
generality, let n be a 4-digit number with decimal representation abed. Then
n = 103 a + 102 b+ lOe+d.
Since 10 == 1 (mod 9), we have 10'< == lk = 1 (mod 9) for any nonnegative integer k.
Consequently,
n = 103 a+ 102 b+ lOe+d == l· a+ 1 · b+ 1· e+d (mod 9).
You don't need to use congruence notation, but it is a convenient shorthand, and it
may help you to systematize your thinking. The important thing is to be aware of the
possibility that an invariant may be a quantity modulo m for a properly chosen m.
Example 3.4. 12 A bubble chamber contains three types of subatomic particles: 10
particles of type X, 11 of type Y, 111 of type Z. Whenever an X-and Y-particle collide,
they both become Z-particles. Likewise, Y-and Z-particles collide and become X
particles and X-and Z-particles become Y-particles upon collision. Can the particles
in the bubble chamber evolve so that only one type is present?
Solution: Let us indicate the population at any time by an ordered triple (x,y, z).
Let's experiment a bit. We start with the popUlation (10,11, 111). If an X-and Y- par
ticle then collide, the new popUlation will be (9,10,11 3 ). Is there anything invariant?
Notice that there is still 1 more Y-particle than X-particles, as before. However, where
there were originally 100 more Z's than Y's, now there are 103 more. Doesn't look
good, but let's stay loose and experiment some more. Another X-Y collision yields
(8,9 , 11 5). The population gap between X and Y is still 1, but the gap between Y
and Z has grown to 10 6. Now let's have an X-Z collision. Our new population is
(7,11, 114). The X-Y gap has grown from 1 to 4, while the Y-Z gap dropped back to
10 3.
If you are not attuned to the possibility of modular arithmetic, the evolution of
population gaps from 1 to 4 or from 100 to 103 to 106 back to 103 may seem chaotic.
But by now you have guessed that
The population gaps are invariant modulo 3.
To prove this formally, let (x, y, z) be the population at a certain time. Without loss of
generality, consider an X-Z collision. The new population becomes (x - 1 ,y+ 2, z - 1 )
and you can easily verify that the difference between the X-and Z-populations is
unchanged, while the difference between the X-and Y-populations has changed by 3
(likewise for the difference between the Z- and Y-populations).