THE PROPS FOR this problem are a chessboard and 32 dominoes. Each domino is of such size that it exactly covers two adjacent squares on the board. The 32 dominoes therefore can cover all 64 of the chessboard squares. But now suppose we cut off two squares at diagonally opposite corners of the board and discard one of the dominoes. Is it possible to place the 31 dominoes on the board so that all the remaining 62 squares are covered? If so, show how it can be done. If not, prove it impossible.

The answer

It is impossible to cover the mutilated chessboard (with two opposite corner squares cut off) with 31 dominoes, and the proof is easy. The two diagonally opposite corners are of the same color. Therefore their removal leaves a board with two more squares of one color than of the other. Each domino covers two squares of opposite color, since only opposite colors are adjacent. After you have covered 60 squares with 30 dominoes, you are left with two uncovered squares of the same color. These two cannot be adjacent, therefore they cannot be covered by the last domino. Suppose two cells of opposite color are removed from the chessboard. Can you prove that no matter which two cells are removed, the board can always be covered with 31 dominoes? For a simple, elegant proof that this is always