Dominoes on a Chessboard

Covering a chessboard with L-shaped and straight trominoes posed two different but very engaging problems. Using larger polyominoes naturally leads to a variety of problems. Perhaps unexpectedly, even the simplest of them - dominos - still afford genuine mathematical entertainment.

A domino is a 2×1 polyomino piece, i.e., a piece that consists of two adjoined squares. Obviously, any rectangular N×M chessboard can be covered with dominoes iff at least one of N and M is even. If both are odd, an empty square can be chosen arbitrarily on the board. The proof is similar to a construction used to solve another problem. So, what else the dominoes are good for? Here's one example.

Discussion

An important observation is that a chessboard line on a 6×6 board can't be crossed by exactly 1 domino. For, such a line would then split the board into two parts of dimensions 6×t and 6×(6-t), each with an even number of squares of which one square is occupied with a half-domino at hand. If the line is not crossed by another domino, then each of the parts is left with an odd number of squares fully covered with dominoes. A contradiction.

Thus it takes at least two dominoes to cross a line. On a 6×6 board there are 10 lines. It takes 10·2 = 20 dominoes to cross all of them. But 20 dominoes cover 40 squares whereas a 6×6 board has only 36 of them. It follows that any covering of the 6×6 board is bound to leave some fault lines. The picture below gives an example of a covering with a single such line.

In general, an N×M board can be covered fault-free iff the following condition hold:

1. N·M is even,

2. N > 4 and M > 4,

3. (N, M) (6, 6)!.

References

1. A. Engel, Problem-Solving Strategies, Springer Verlag, 1998, p. 35
2. S. Golomb, Polyominoes, Princeton University Press; 2nd edition (March 18, 1996)
3. C. W. Trigg, Mathematical Quickies, Dover, 1985, #258

Copyright © 1996-2010 Alexander Bogomolny

Copyright © 1996-2005 Alexander Bogomolny