Two squares of opposite colour are removed from an 8 by 8 chessboard, anywhere on the board. Can the remaining 62 squares always be tiled by 31 dominoes? Give the argument, and say why the usual colouring argument does not settle it.

Two squares of opposite colour are removed from an 8 by 8 chessboard, anywhere on the board. Can the remaining 62 squares always be tiled by 31 dominoes? Give the argument, and say why the usual colouring argument does not settle it.

Approach: The colouring only rules cases out. For the positive direction find a single closed route through all 64 squares and see what deleting two of them does to it.

Yes, a tiling always exists. Every domino covers one white and one black square, so removing two squares of the same colour leaves 32 and 30 and no tiling is possible. That colouring parity argument proves impossibility only and gives no construction when the two removed squares differ in colour. For that case use a Hamiltonian cycle through all 64 squares of the board, which exists on an 8 by 8 grid and alternates colour as it goes. Deleting two squares of opposite colour cuts the cycle into two arcs, each of even length because the colours alternate. Consecutive squares along an arc are adjacent, so pairing them off tiles each arc, giving 31 dominoes in total. The argument needs the Hamiltonian cycle, so it does not carry over to a 3 by 3 board.

Follow-up: On a 6 by 6 board with two squares of opposite colour removed, can a 1 by 3 tromino tiling of the remaining 34 squares ever exist?

Key concepts: colouring parity, hamiltonian cycle, domino tiling.