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?
Answer
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.
No comments:
Post a Comment