13
$\begingroup$

Suppose you have a checkerboard with two opposite corner squares removed, like this:

Mutilated chessboard

Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?

$\endgroup$
  • $\begingroup$ Hm is the chess tag appropriate here? This question isn't really about chess per se. $\endgroup$ – arshajii May 19 '14 at 15:29
  • $\begingroup$ Well, the problem is called the mutilated chess board problem. $\endgroup$ – Mohit Punjabi May 19 '14 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$ – arshajii May 19 '14 at 15:35
  • $\begingroup$ A similar argument could be stated for this problem. I started a discussion on meta about this. $\endgroup$ – Mohit Punjabi May 19 '14 at 15:42
12
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.