1
$\begingroup$

Can someone explain the proof behind why the mutilated chessboard problem is unsolveable? The problem asks, given an 8x8 chessboard with two diagonally opposite corners removed, is it possible to fill the entire board with 31 dominos (assuming that each domino covers 2 adjacent squares)?

The classic solution to this problems states that when you cut two diagonal corners, you always cut away two squares of the same color, meaning that your board has an unequal number of black and white squares. Thus it is impossible to cover the board completely with dominos (since each domino must cover a black and white square).

Chessboard with corners removed

However I'm not convinced this is an adequate proof on its own. Imagine a different 8x8 board where each row alternates between black and white (so the first row is 8 black squares, then the second row is 8 white squares, ect). If you remove two opposite corners of this board then you'll remove one white and one black square, meaning you'll be left with the same number of white and black squares. However aside from the color arrangement this is still clearly the same board.

Alternate chessboard with corners removed

Is there something about the above proof that I'm not getting? Or is this one of those proofs that sounds neat but doesn't actually hold up?

$\endgroup$
2
  • 4
    $\begingroup$ In your revised board, must a domino cover exactly one black and one white square? $\endgroup$ Nov 1 '19 at 3:49
  • 3
    $\begingroup$ "However aside from the color arrangement this is still clearly the same board." Yes, and other than that, Mrs. Lincoln, how did you enjoy the play? I don't think there's any proof in all of mathematics that you can't spoil by replacing essential parts of the argument with irrelevant mangled alternative facts like you've done here. $\endgroup$
    – David K
    Nov 1 '19 at 4:01
6
$\begingroup$

The proof with the first coloring works for this particular problem. The proof for the second doesn’t. That’s really the end of the matter.

You can try to make the argument more formal if that makes more sense to you. Assign a coordinate to each square on the chessboard, so that the top left corner is at $(1,1)$, and the bottom right corner is at $(8,8)$. The “white” squares will now correspond to the squares whose coordinates add to an even number, while the “black” squares will have coordinates that add to an odd number. It’s easy to see that when we remove both previously mentioned corners, we’re left with $32$ black squares, and $30$ white squares. However, a domino, which spans two adjacent squares, must necessarily cover both a white and a black square. Therefore, any valid covering must cover the same number of white and black squares, which means it’s impossible to cover up the whole mutilated board.

Your second coloring not working is just a consequence of the proof above not working for the corresponding modified definitions of the “white” and “black” squares. But a proof not working does not at all imply that another one is false.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks, after stepping away for a bit I realized that I was missing the point of the proof. On a chessboard with alternating colors, a 2x1 domino must always cover one of each color. The fact that doesn't hold true on alternate colorings doesn't affect the truth of the first scenario. $\endgroup$
    – Paulrog
    Nov 1 '19 at 4:27

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.