Page 125 - Discrete Mathematics and Its Applications

104 1 / The Foundations: Logic and Proofs
FIGURE 4 Tiling the Standard Checkerboard.
EXAMPLE 20
FIGURE 5 The Standard Checkerboard
with the Upper Left and Lower Right
Squares Removed.
squares because each domino covers two squares and no two dominoes overlap and no dominoes
overhang the board. Consequently, we can prove by contradiction that a standard checkerboard
with one square removed cannot be tiled using dominoes because such a board has an odd
number of squares. ▲
We now consider a trickier situation.
Can we tile the board obtained by deleting the upper left and lower right corner squares of a
standard checkerboard, shown in Figure 5?
Solution: A board obtained by deleting two squares of a standard checkerboard contains
64 − 2 = 62 squares. Because 62 is even, we cannot quickly rule out the existence of a tiling of
the standard checkerboard with its upper left and lower right squares removed, unlike Example
19, where we ruled out the existence of a tiling of the standard checkerboard with one corner
square removed. Trying to construct a tiling of this board by successively placing dominoes
might be a first approach, as the reader should attempt. However, no matter how much we try,
we cannot find such a tiling. Because our efforts do not produce a tiling, we are led to conjecture
that no tiling exists.
We might try to prove that no tiling exists by showing that we reach a dead end however
we successively place dominoes on the board. To construct such a proof, we would have to
consider all possible cases that arise as we run through all possible choices of successively
placing dominoes. For example, we have two choices for covering the square in the second
column of the first row, next to the removed top left corner. We could cover it with a horizontally
placed tile or a vertically placed tile. Each of these two choices leads to further choices, and so
on. It does not take long to see that this is not a fruitful plan of attack for a person, although a
computer could be used to complete such a proof by exhaustion. (Exercise 45 asks you to supply
such a proof to show that a 4 × 4 checkerboard with opposite corners removed cannot be tiled.)
We need another approach. Perhaps there is an easier way to prove there is no tiling of a
standard checkerboard with two opposite corners removed. As with many proofs, a key obser-
vation can help. We color the squares of this checkerboard using alternating white and black
squares, as in Figure 2. Observe that a domino in a tiling of such a board covers one white square
and one black square. Next, note that this board has unequal numbers of white square and black