Associated Topics || Dr. Math Home || Search Dr. Math

### Tiling a Mutilated Chessboard With Dominoes

```Date: 08/29/2003 at 15:51:54
From: David
Subject: tiling a chessboard

Suppose we take an ordinary chess board and randomly remove a
black square and a white square. Is it always possible to cover what
remains with 2x1 dominoes? If yes, how? If no, why not?

A domino covers 1 black square and 1 white square, so for this to
work there has to be an equal number of white and black squares, and
there are. So it seems the answer is yes, but I can't prove it!
```

```
Date: 08/31/2003 at 08:33:22
From: Doctor Jacques
Subject: Re: tiling a chessboard

Hi David,

It is true that the two squares must be of different colors for the
problem to have a solution, for the reason you mention. However, by
itself, this does not ensure that the condition is sufficient. The
normal way of proving that would be to give a procedure for placing
the dominoes, and to prove that the procedure always works.

We start with a chessboard of 8 by 8 squares (any even size would
do), from which we have removed a black square and a white square. We
will try to cover the remaining squares with dominoes.

We will first prove a preliminary result:

If we manage to fill a rectangle containing the two missing
squares, we can complete the job.

To see this, assume that we have completely tiled an m by n rectangle:

+-----------+
|           |
m |           |
|           |
+-----------+
n

and that the rectangle contains the two removed squares. The dominoes
in the rectangle cover an even number of squares and, if we add the
two removed squares, we still have an even number. As we assume that
the rectangle is completely tiled, this shows that the rectangle
contains an even number of squares, and therefore, the product m*n is
even.

We can conclude that at least one of m or n is even (otherwise the
product would be odd); let us assume, for example, that m (the height
of the rectangle) is even. We can then place vertical dominoes to the
left and to the right of the rectangle, to add columns of height m,
until we reach the sides of the board. We now have an m by 8
rectangle:

+---+------+-+
|:::|      |:|
m |:::|      |:|
|:::|      |:|
+---+------+-+
8

Now, the width of the rectangle is even (8, or the size of the
board), and we can add horizontal dominoes above and below the
rectangle to complete the tiling of the whole board.

To summarize, we only need to fill a rectangle containing the two
removed squares; in fact, we will show that we can fill the smallest
possible such rectangle. There are three cases to consider:

1. The two removed squares are in the same row
2. The two removed squares are in the same column.
3. Neither of the above.

Case 1 - Same row
-----------------
In this case, as the squares are of opposite color, there is an even
number of squares between them, say 2n. We can fill these squares
with n horizontal dominoes. This gives us a completely filled
rectangle, of size 1 by (2n+2), and, by what has been said above, we
can fill the rest of the board. Note that it is also possible to have
n = 0, i.e. the squares adjacent to each other.

Case 2 - Same column
--------------------
The argument is the same as in case 1, using vertical dominoes
instead. You can also imagine turning the board 90 degrees, solving
case 1, and then putting the board back in its original position. :)

Case 3 - Different rows and columns
-----------------------------------
In this case, we have the following configuration:

+----------+
|*         |
m |          |
|         *|
+----------+
n

where each "*" represents a removed square. Note that, if the
removed squares (the corners of the rectangle) have opposite colors,
one of the numbers m, n must be even and the other one must be odd.
(Do you see why?). Let us assume, for example, that m is odd and n
is even.

As m is odd, the first and last columns contain each (m-1) free
squares, and (m-1) is even. We can therefore fill these columns with
vertical dominoes.

This leaves us with a rectangle of size m by (n-2). As n-2 is even,
we can fill that rectangle with horizontal dominoes, one row at a
time. In the drawing below, I used "|" for vertical dominoes, and "-"
for horizontal dominoes:

+----------+
|*--------||
m ||--------||
||--------*|
+----------+
n

This gives us a completely filled rectangle containing the removed
squares, and, by what has been said before, we can also complete the
board in this case.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search