Please explain the proof of the Mutilated Chessboard Problem

Question

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).

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.

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?

Answer 1

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.