The Art and Craft of Problem Solving

3.4 INVARIANTS 99

The first insight is to discover an appropriate penultimate step. Let us call the
property of having at least one integral side "good." How do we show that the large
rectangle is good? Orienting it so that the lower-left comer is a lattice point is the key:

If the rectangle weren't good, then it would have only one lattice point

corner. But if the rectangle is good, then it will have either two lattice

point corners (if one dimension was an integer), or fo ur lattice point

corners (if both length and width are integers).

In other words, parity plays a role: a rectangle with lower-left comer at a lattice
point is good if and only if the number of comer lattice points is even! Let us count
lattice point comers, hoping to show that the number of lattice point comers for the
big rectangle must be even.
Of course we must use the hypothesis that each of the smaller rectangles is good.
Consider the comers of a small rectangle. It may have no lattice point comers, or
it may have two or four, but can never have just one or three, because of goodness.
Consequently, if we count the number of comer lattice points on each small rectangle
and add them up, the sum, which we will call S, will be even.
But we overcounted some of the lattice points. For example, in the picture above,
all the corner lattice points are indicated by circles. There are ten rectangles with
comer lattice points, and each has exactly two comer lattice points, so S = 20. The
white circles were counted exactly once, the gray ones were counted twice, and the
black one was counted four times. So another way to count the sum S is

S = 1. (# white circles) + 2. (# gray circles) + 4. (# black circles)

= 1 ·2 + 2·7 + 4· 1 = (^20).
In general, when we compute the sum S, we will overcount at some comers. Here
are two simple observations that are easy to check.

• We will count a comer point only once, twice or four times-never three times.


• The only comer points that are counted exactly once are the comers of the large
  rectangle.
  Coloring the lattice point comers as in our example, we see that if w, g, b denote
  the number of white, gray, and black circles, then

S = w+2g+4b.

Thus w = S -2g -4b is the number of comer lattice points of the large rectangle. And
since S is even, S -2g -4b is also even: the large rectangle must be good! •

This solution is quite instructive. A terse outline that an experienced problem
solver could understand might be, "Orient the large rectangle so that one comer is a
lattice point, then consider the parity of the number of comer lattice points." There
were two crux moves to this brilliant solution: first anchoring the lower-left comer
on a lattice point (yielding "free" information) and then deducing the parity rule for
goodness. The rest was a fairly standard argument (as you will see in Chapter 6, the
tactic of counting something in two or more different ways is a pervasive one).