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!

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/