Remove any black square and any white square, then tile

Question

From an 8 by 8 chessboard, remove one black square and one white square, chosen anywhere on the board. Sixty-two squares remain, 31 black and 31 white. Prove that the remaining board can always be covered exactly by 31 dominoes, each covering two adjacent squares. The colour count is necessary (that is why removing two same-colour corners fails), but it is not obviously sufficient. You need a construction that works for every choice of the two squares.

Accepted Answer

Yes, always. The proof uses a closed tour of the board. A closed tour. It is easy to draw a loop through all 64 squares that moves only between edge-adjacent squares: go up the first column, then snake back and forth through columns 2 to 8 in the rows 2 to 8, and come home along row 1. (Any such "rook's tour" that returns to its start works.) Along this loop the colours alternate black, white, black, white, because adjacent squares always differ in colour. Removing two squares of opposite colour. The loop is a ring of 64 squares. Cutting out one black and one white square breaks the ring into…

Remove any black square and any white square, then tile

Your answer

Discussion

Learn the concepts

Related questions