The Art and Craft of Problem Solving

3.4 INVARIANTS 101

We conclude the solution by noting that the initial population was (10, II, Ill).
The X-Y population gap is 1, and hence it must always be congruent to I modulo 3.
Thus there is no way that the X-and Y-populations can ever be the same, so these pop­
ulations can never both become zero. The same argument holds for other population
pairs: it is impossible for two of the populations to become zero. _

The use of coloring is related to parity and modular arithmetic, except that we are
not constrained by the algebraic properties of integers. An example of coloring was
the domino problem (Example 2.4.2 on page 54 ), which could have been recast as a
parity problem. Here is another example, using 12 colors.

Example 3.4.13 Is is possible to tile a 66 x 62 rectangle with 12 x 1 rectangles?

Solution: Obviously, any large rectangle that is tiled by 12 x I rectangles must
have an area that is divisible by 12. Indeed, 66 ·62 = 12 · 34 1. So impossibility has not
yet been ruled out. Nevertheless, experimenting with smaller configurations with the
same property (i.e., m x n where neither m nor n is a multiple of 12, yet mn is) leads
us to conjecture that the 66 x 62 rectangle cannot be tiled with 12 x 1 rectangles.
So let's assume that there is a tiling, and we shall look for a contradiction. Color
the squares of 66 x 62 rectangle with 12 colors in a cyclic "diagonal" pattern as follows
(we are assuming that the height is 66 and the width is 62):

I 12 11 ... I 12

2 I 12 ... 2 1

3 2 I ... 3 2

5 4 3 ... 5 4
6 5 4 ...^6 5
This coloring has the nice property that any 12 x 1 rectangle in the tiling consists
of 12 differently colored squares. If the large rectangle can be tiled, it will be tiled
by 66. 62/ 12 = 34 1 12 x I rectangles, and hence the large rectangle must contain 341
squares in each of the 12 colors. The important thing is not the number 34 1, but the fact
that each color occurs in the same number of squares. We will call such a coloration
"homogeneous."
Let's look more closely at the colored 66 x 62 rectangle. We can break it up into
four sub-rectangles:

60 x 60 60 x 2

6 x6 0 6x2

It is easy to check that the 60 x 60, 60 x 2 and 6 x 60 sub-rectangles are all homo­

geneous, since each of these sub-rectangles has a dimension that is a multiple of 12.

But the 6 x 2 sub-rectangle is colored as follows: