Mutilated Chessboard Problem

In this article, I would like to talk about an old problem in mathematics called the Mutilated Chessboard problem and how to solve it with coloring proof. This proof can transform how we think about the problem and make it easier to reason about the problem.

Problem Statement:

Figure 1. (left) 8x8 Mutilated Board and (right) 2x1 Tile

Given an 8 x 8 mutilated board in Figure 1(left), could we cover all the board with 31 pieces of 2 x 1 tile in Figure 1(right)?

Comment and Analysis of the problem:

First of all, we count the number of squares inside the board. If we consider the non-mutilated version, it should have 8 x 8 = 64 squares. Since we removed 2 of the corner squares, the number of squares should be 62.

The 2 x 1 tile consist of 2 squares, hence 31 pieces of tile have 62 squares as well.

Observation 1: Since the mutilated board and 31 pieces of tile have same number of squares, hence, to cover the board with the tiles we must place all the tiles on the board without any overlap.

Now, let us try to cover the board manually to get more intuition on the problem and probably if we are lucky enough, we might cover the board and have the solution. Figure 2 shows 2 samples of trials to manually cover the board.

Figure 2. Samples of trials to cover the board

In our tries in Figure 2, we failed to cover the board and in both tries we can only put 30 tiles on the board. At this point, we might develop the intuition that it may be impossible to have a full covering of the board. However we still can’t say for sure.

*Notes: One possible solution is to exhaustively try all the possible arrangement of the covering and see whether we can actually cover the board, but this solution doesn’t give us any reasoning why and not extendable to a bigger board.

Solution:

We will solve this problem with a method called coloring proof. The coloring proof works by assigning colors to some elements of the problem and the colors will help us to reason about problem.

For this particular problem, let’s color the squares into alternating black and white color (like a chess board), see Figure 3 for visualization.

Figure 3. Colored Mutilated Board and Tile

Observation 2: The colored 8x8 mutilated board is a chess board with 2 black squares on the corners removed.

Let us count the number of white squares and black squares for the board and tile.

• The board:
  A normal chess board have 32 black squares and 32 white squares, since a mutilated board have 2 black squares removed (observation 2), hence the board has 30 black squares and 32 white squares.
• The tiles:
  Each tile has one black square and one white square. So 31 pieces of tile will have 31 black squares and 31 white squares.

Observation 3: When we put a tile into the board, we can always rotate the tile so that it has matching color with the board, i.e. the white square on top of a white square and the black square on top of a black square.

Observation 3 implies that if the tiles cover all the board, then they must have the same number of black squares and white squares. However, as we counted, the board and the tiles do not have the same number of black squares (30 vs 31) and white squares (32 vs 31). In conclusion, it is not possible to cover the board with the tiles. Q.E.D.

Comment on the solution:

From the coloring proof, our previous intuition actually transforms into a firm belief that it is indeed impossible to cover the board with the tiles since the number of colored (white and black) squares do not match.

Moreover, we have a deeper understanding of the problem itself. For example, we could have the following benefits:

1. We could solve a bigger problem with the same method.
   Suppose we have mutilated 100 x 100 board with upper-left and bottom-right corner squares removed, we could solve it with the same method.
2. From our tries in Figure 2, we could know why only 30 tiles are possible and we could even reason that the non-colored squares should have white color on Figure 3

Afterword:

This is actually my first article and I hope this is useful for the readers. I especially want to spark the interest of the readers on problem-solving. For those who want to know more about coloring proof, I recommend seeing more problems in chapter 2 of Problem Solving Strategies by Arthur Engel.

I would love to know more about your thoughts and possibly any topics you are interested in.

Finally, thanks for reading!

The Math Scientist