Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

Does this help?  Write back if you'd like to talk about this 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/