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

### Covering a Checkerboard after Removing a Random Square

```Date: 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!

```

```
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.

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/
```
Associated Topics:
College Discrete Math
High School Discrete Mathematics
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