Covering a Checkerboard after Removing a Random SquareDate: 05/11/2008 at 16:14:58 From: Roula Subject: Checkerboard problem, removing any one square Use mathematical induction to prove that for any positive integer n, if any one square is removed from a 2^n x 2^n checkerboard, then the remaining squares can be completely (and exactly) covered with L-shaped pieces composed of three squares. I'm not sure if I understand how to create a formula that would hold for all values of 'n'. I came up with, (2^2n - 1) mod 3 = 0; I think that because we remove one square we have to minus one and this has to be divisible by 3 (because we have to cover the rest of the checkerboard with 3 L-shaped dominoes). I'm not sure if this is correct. And, how do I prove it for all cases of n? Any help or pointers in the right direction will be greatly appreciated! Thanks in advance! Date: 05/11/2008 at 18:17:10 From: Doctor Greenie Subject: Re: Checkerboard problem, removing any one square Hi, Roula -- A very nice problem!! I will try to answer it... but the "proof" will be a bit informal; and, since I can't draw nice figures, it might be rather difficult to understand. There is much more involved than just showing that the number 2^2n - 1 is divisible by 3. You have to show that the checkerboard with one square removed can be covered by L-shaped pieces that cover 3 squares each. (For example, in a famous problem, the opposite corner squares of an 8-by-8 checkerboard are removed, leaving 62 squares, and you are asked to find a way to cover the remaining squares with 1-by-2 tiles. It can't be done. Each tile covers 2 squares, and 62 is divisible by 2. But the problem can't be solved, because the opposite corner squares are the same color, and each 1-by-2 tile covers one square of each color. You can't cover the remaining 62 squares--of which 32 are one color and 30 are the other color--with tiles that each cover one square of each color.) A "proof" by mathematical induction does not have to be purely mathematical. Although it is difficult to demonstrate in a typed message, and although the strict formality of a mathematical proof by mathematical induction is hard to maintain, a geometric proof by mathematical induction is possible. To start with, consider the case for n=1--i.e., the case of the 2- by-2 checkerboard. If any one square is removed, then the remaining three squares constitute one of the prescribed L-shaped pieces. So the proposition is true for n=1. Now consider the case for n=2--a 4-by-4 checkerboard, with one square removed. Divide the 4-by-4 square into four 2-by-2 squares. In the 2-by-2 square containing the square that has been removed, complete that 2-by-2 square using one of the L-shaped pieces. That leaves us with three 2-by-2 squares to be covered with our L-shaped pieces. To cover those three remaining 2-by-2 squares with L-shaped pieces, start by placing the next L-shaped piece so that the three squares that make up the piece each lie in one of the three remaining 2-by-2 squares, leaving the square closest to the original center of the board uncovered. Do that for each of the three 2-by-2 squares. Now each of those 2-by-2 squares has one square uncovered, and the remaining part of each can be covered by one of the L-shaped pieces. What about the case for n=3--an 8-by-8 checkerboard? We can use the same strategy to show that it too can be covered by our L-shaped pieces. First divide the 8-by-8 square into four 4-by-4 squares, and cover the 4-by-4 square containing the missing square as described above. Then place the next L-shaped piece so that one square of it is in each of the other three 4-by-4 squares. That will give you three 4-by-4 squares each with one piece already covered--but we know that we can cover the remaining parts of those 4-by-4 squares with our L-shaped pieces. The rigor of a mathematical proof by induction is hard to put in place--but I hope you can see that the strategy for covering any 2^n-by-2^n checkerboard with one square removed can be followed. Following is an attempt to demonstrate the process for covering an 8- by-8 square with one random square removed using L-shaped pieces. In the diagrams, the X represents the missing square; O represents a square that has not yet been covered; and lower-case letters represent the L-shaped pieces--three of the same letter in an L- shaped configuration represent one L-shaped piece. We start with the 8-by-8 checkerboard with one square removed: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O X O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O We divide the 8-by-8 square into four 4-by-4 squares and then divide each of those 4-by-4 squares into four 2-by-2 squares to identify the 2-by-2 square containing the missing square; and we place our first L-shaped piece to finish covering that 2-by-2 square: O O O O O O O O O O O O O O O O O O O O O O a a O O O O O O X a O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O Next we identify the 4-by-4 square containing the 2-by-2 square that we just finished covering, and we identify the other three 2-by-2 squares that make up that 4-by-4 square. And we place our next L- shaped piece so that it covers one square of each of those other three 2-by-2 squares: O O O O O O O O O O O O O b b O O O O O O b a a O O O O O O X a O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O And then we use one L-shaped piece to finish covering each of those other three 2-by-2 squares: O O O O d d e e O O O O d b b e O O O O c b a a O O O O c c X a O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O We have finished covering one of the four 4-by-4 squares. Next we place one of the L-shaped pieces so that it covers one square of each of the remaining three 4-by-4 squares: O O O O d d e e O O O O d b b e O O O O c b a a O O O f c c X a O O O f f O O O O O O O O O O O O O O O O O O O Now each of the remaining three 4-by-4 squares has one corner square covered. But from our earlier work, we already know that we can use our L-shaped pieces to cover the remaining part of a 4-by-4 square which already has a corner square covered. And so we know we are going to be able to finish covering the 8-by-8 square with our L- shaped pieces. I leave the details for finishing this example to you. And I leave it to you to try to put this analysis into the form of a formal proof by mathematical induction.... Thanks for sending an interesting problem. I got a good dose of good mental exercise from working on it! - Doctor Greenie, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/