Tiling a Mutilated Chessboard With DominoesDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/