Question

Consider an m-by-n chessboard with m and n both odd. To fix the notation, suppose that the square in the upper left-hand corner is colored white. Show that if a white square is cut out anywhere on the board, the resulting pruned board has a perfect cover by dominoes.

Answer 1

There are two cases to consider.

A) The removed square is in an odd-numbered column (and row). In this case, the board is divided by that column and row into parts with an even number of columns, which can always be tiled by dominos, and the column the square is in, which has an even number of remaining squares that can also be tiled by dominos.

B) The removed square is in an even-numbered column (and row). In this case, the top row to the left of that column (including that column) can be tiled by dominos, as can the bottom row to the right of that column (including that column). The remaining untiled sections of the board have even numbers of rows, so can be tiled by dominos.

_____

Perhaps the shorter answer is that in an odd-sized board, the corner squares are the ones that there is one of in excess. Cutting out one that is of that color leaves an even number of squares, and equal numbers of each color. Such a board seems like it ought to be able to be tiled by dominos, but the above shows there is actually an algorithm for doing so.