Suppose you have cut off the two diagonally opposite corner squares of a regular 8×8 square board, as shown above, 62 squares remain. Now you have a set of 2×1 dominoes, each of which covers two squares that are adjacent vertically or horizontally. Is it possible to use 31 of these dominoes to tile all 62 squares?

No. Picture the 8x8 board as a chess board. Then two diagonally opposite squares would be of the same color . Now, we have 30 black and 32 white squares. Each domino would have to cover precisely 1 white and 1 black which would make allow filling only 60 squares. i.e., maximum 30 dominoes.

ReplyDelete