Prove that if you remove any two squares of opposite colors from a chessboard, the board can be covered...

geometry/tiling/dominoes.two.holes New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

Prove that if you remove any two squares of opposite colors from a
chessboard, the board can be covered with 31 dominoes.

-- Ross Millikan <millikan.ross@ssd.loral.com>

[ Editor: posted as a follow-up to the problem of the chessboard with
two opposite corners removed, which cannot be covered (see the list in
logic/aha.puzzles). ]

Show solution

We'll prove by induction on n that any 2k x n board (k > 0, n > 1) with
two holes of opposite colours can be tiled with dominoes.

Base case (n = 2).  Up to symmetry, the board looks either like this,
with m >= 0 and r >= 0:

       ._._._     _._._._     _._._._     _._._.
       |_|_|_ ... _|X|_|_ ... _|_|X|_ ... _|_|_|
       |_|_|_     _|_|_|_     _|_|_|_     _|_|_|

        \---------/   \---------/   \---------/
         m squares     2r squares    2(k-r-1)-m

or like this:

       ._._._     _._._._     _._._._     _._._.
       |_|_|_ ... _|X|_|_ ... _|_|_|_ ... _|_|_|
       |_|_|_     _|_|_|_     _|_|X|_     _|_|_|

        \---------/   \---------/   \---------/
         m squares    2r+1 squares  2(k-r-1)-m-1

or else the two holes are next to each other in different rows.  In all
three cases it is obvious how to tile it with dominoes.

Induction step.  Suppose the board has n+1 rows (n>1).  Look at the
bottom row of the board.  If it has no hole, then we tile it with k
dominoes and reduce the board to 2k x n, which we know can be tiled by
the induction hypothesis.  [ Editor: the start of the next sentence
is missing in the original. ] has a hole, and we
can tile 2k-2 of the remaining 2k-1 squares with k-1 dominoes, leaving
one uncovered square adjacent to the hole.  We then put a domino in
that square, sticking out into the row above, like this:

            ._______________.
         /  |               |  \
         |  |               |  |
         |  |               |  | n
     n+1 |  |               |  |
         |  |               |  |
         |  |         ._.   |  |
         |  |___.___._| |___|  /
         \  |___|___|X|_|___|

The square just covered in row n must be of the same colour as the
missing square from row n+1 (as the two squares are diagonally
adjacent), so we consider the square just covered in row n to be
missing from the 2k x n board and tile it by the induction hypothesis.

If the bottom row has two holes, it may be possible to tile the bottom
row with k-1 dominoes, leaving a 2k x n board with no holes, which is
easy to tile.  If not, we tile the bottom row with k-2 dominoes leaving
two uncovered squares adjacent to the two holes, and proceed similar to
the above.

-- Gareth Rees <gdr11@cl.cam.ac.uk>  (June 1995)