Suppose you have a checkerboard with two opposite corner squares removed, like this:
Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?
Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.Sign up to join this community
This puzzle is known as the mutilated chessboard problem. The other answer correctly explains that such a covering is impossible because it would require an equal number of black and white squares (since each domino must cover one black and one white square), which the corner-cut board does not have.
The link above contains a slightly more general result as well:
The same impossibility proof shows that no domino tiling exists whenever any two white squares are removed from the chessboard. However, if two squares of opposite colors are removed, then it is always possible to tile the remaining board with dominos; this result is called Gomory's theorem, and is named after mathematician Ralph E. Gomory, whose proof was published in 1973. Gomory's theorem can be proven using a Hamiltonian cycle of the grid graph formed by the chessboard squares; the removal of two oppositely-colored squares splits this cycle into two paths with an even number of squares each, both of which are easy to partition into dominos.
Each domino would occupy one black and one white cell. So, 31 dominoes would require exactly 31 white, and 31 black cells.
The chessboard given, however, has 32 white and 30 black cells making it impossible to place the dominoes.