Page 124 - Discrete Mathematics and Its Applications

1.8 Proof Methods and Strategy 103

FIGURE 3
FIGURE 2 The Standard Checkerboard. Two Dominoes.

the development of new parts of mathematics. We will mention a few famous conjectures later
in this section.

Tilings

We can illustrate aspects of proof strategy through a brief study of tilings of checkerboards.
Looking at tilings of checkerboards is a fruitful way to quickly discover many different results
and construct their proofs using a variety of proof methods. There are almost an endless number
of conjectures that can be made and studied in this area too. To begin, we need to define some
terms. A checkerboard is a rectangle divided into squares of the same size by horizontal and
vertical lines. The game of checkers is played on a board with 8 rows and 8 columns; this
board is called the standard checkerboard and is shown in Figure 2. In this section we use the
term board to refer to a checkerboard of any rectangular size as well as parts of checkerboards
obtained by removing one or more squares. A domino is a rectangular piece that is one square
by two squares, as shown in Figure 3. We say that a board is tiled by dominoes when all its
squares are covered with no overlapping dominoes and no dominoes overhanging the board. We
now develop some results about tiling boards using dominoes.

EXAMPLE 18 Can we tile the standard checkerboard using dominoes?

Solution:We can find many ways to tile the standard checkerboard using dominoes. For example,
we can tile it by placing 32 dominoes horizontally, as shown in Figure 4. The existence of one
such tiling completes a constructive existence proof. Of course, there are a large number of other
ways to do this tiling. We can place 32 dominoes vertically on the board or we can place some
tiles vertically and some horizontally. But for a constructive existence proof we needed to find
just one such tiling. ▲

EXAMPLE 19 Can we tile a board obtained by removing one of the four corner squares of a standard checker-
board?

Solution: To answer this question, note that a standard checkerboard has 64 squares, so removing
a square produces a board with 63 squares. Now suppose that we could tile a board obtained
from the standard checkerboard by removing a corner square. The board has an even number of