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?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Hm is the chess tag appropriate here? This question isn't really about chess per se. $\endgroup$– arshajiiCommented May 19, 2014 at 15:29
-
$\begingroup$ Well, the problem is called the mutilated chess board problem. $\endgroup$– John BupitCommented May 19, 2014 at 15:34
-
$\begingroup$ But it's about the chess board, not the game of chess. It could just as well have been about a checker board. $\endgroup$– arshajiiCommented May 19, 2014 at 15:35
-
$\begingroup$ A similar argument could be stated for this problem. I started a discussion on meta about this. $\endgroup$– John BupitCommented May 19, 2014 at 15:42
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
No!
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.
answered May 19, 2014 at 14:47