Checkerboard and dominoes

This is a rather well known puzzle, but for good reason.

Puzzle

A regular checker board has 64 squares (arranged in an 8 by 8 square). You happen to have a set of dominoes, each of which can cover exactly 2 squares on the checker board. Suppose you cut out one square from opposite corners. Is it possible to cover this mutilated board with non-overlapping dominoes? That is, is there a way to pair up the remaining 62 squares so that the two squares in each pair are adjacent? Prove your answer.

Help

Expand

Hint

Checkerboards have squares of two different colors.

Expand

Answer

No.

Expand

Solution

The two squares at opposite corners are either both white or both black. In either case, the remaining 62 squares will consist of 30 squares of one color, and 32 squares of the other. No matter how a domino is placed on the board, it will cover exactly one square of each color. Thus it is impossible to cover every remaining square.

See also

Checkerboard cut-up

Longest road