Page 126 - Discrete Mathematics and Its Applications

1.8 Proof Methods and Strategy 105

squares. We can use these observations to prove by contradiction that a standard checkerboard
with opposite corners removed cannot be tiled using dominoes. We now present such a proof.

Proof: Suppose we can use dominoes to tile a standard checkerboard with opposite corners
removed. Note that the standard checkerboard with opposite corners removed contains 64 − 2 =
62 squares.The tiling would use 62/2 = 31 dominoes. Note that each domino in this tiling covers
one white and one black square. Consequently, the tiling covers 31 white squares and 31 black
squares. However, when we remove two opposite corner squares, either 32 of the remaining
squares are white and 30 are black or else 30 are white and 32 are black. This contradicts the
assumption that we can use dominoes to cover a standard checkerboard with opposite corners
removed, completing the proof. ▲
We can use other types of pieces besides dominoes in tilings. Instead of dominoes we can
study tilings that use identically shaped pieces constructed from congruent squares that are
connected along their edges. Such pieces are called polyominoes, a term coined in 1953 by the
FIGURE 6 A mathematician Solomon Golomb, the author of an entertaining book about them [Go94]. We
Right Triomino will consider two polyominoes with the same number of squares the same if we can rotate and/or
and a Straight flip one of the polyominoes to get the other one. For example, there are two types of triominoes
Triomino. (see Figure 6), which are polyominoes made up of three squares connected by their sides. One
type of triomino, the straight triomino, has three horizontally connected squares; the other
type, right triominoes, resembles the letter L in shape, flipped and/or rotated, if necessary. We
will study the tilings of a checkerboard by straight triominoes here; we will study tilings by
right triominoes in Section 5.1.

EXAMPLE 21 Can you use straight triominoes to tile a standard checkerboard?

Solution: The standard checkerboard contains 64 squares and each triomino covers three
squares. Consequently, if triominoes tile a board, the number of squares of the board must be
a multiple of 3. Because 64 is not a multiple of 3, triominoes cannot be used to cover an 8 × 8
checkerboard. ▲

In Example 22, we consider the problem of using straight triominoes to tile a standard
checkerboard with one corner missing.

EXAMPLE 22 Can we use straight triominoes to tile a standard checkerboard with one of its four corners
removed? An 8 × 8 checkerboard with one corner removed contains 64 − 1 = 63 squares. Any
tiling by straight triominoes of one of these four boards uses 63/3 = 21 triominoes. However,
when we experiment, we cannot find a tiling of one of these boards using straight triominoes.
A proof by exhaustion does not appear promising. Can we adapt our proof from Example 20 to
prove that no such tiling exists?

Solution: We will color the squares of the checkerboard in an attempt to adapt the proof by
contradiction we gave in Example 20 of the impossibility of using dominoes to tile a standard
checkerboard with opposite corners removed. Because we are using straight triominoes rather
than dominoes, we color the squares using three colors rather than two colors, as shown in
Figure 7. Note that there are 21 blue squares, 21 black squares, and 22 white squares in this
coloring. Next, we make the crucial observation that when a straight triomino covers three
squares of the checkerboard, it covers one blue square, one black square, and one white square.
Next, note that each of the three colors appears in a corner square.Thus without loss of generality,
we may assume that we have rotated the coloring so that the missing square is colored blue.
Therefore, we assume that the remaining board contains 20 blue squares, 21 black squares, and
22 white squares.
If we could tile this board using straight triominoes, then we would use 63/3 = 21 straight
triominoes. These triominoes would cover 21 blue squares, 21 black squares, and 21 white