Question

Use a proof by exhaustion to show that a tiling using dominoes of a 4 × 4 checkerboard with opposite corners removed does not exist. [Hint: First show that you can assume that the squares in the upper left and lower right corners are removed. Number the squares of the original checkerboard from 1 to 16, starting in the first row, moving right in this row, then starting in the leftmost square in the second row and moving right, and so on. Remove squares 1 and 16. To begin the proof, note that square 2 is covered either by a domino laid horizontally, which covers squares 2 and 3, or vertically, which covers squares 2 and 6. Consider each of these cases separately, and work through all the subcases that arise.]

Short answer

A tiling that uses dominoes of a checkerboard with opposite corners removed does not exist.

Step-by-step solution

Introduction

A standard checkerboard is a board with 8 rows and 8 columns, forming squares of equal size.

A domino is a rectangle, equal to the size of two squares attached either horizontally or vertically.

A board is tiled by dominoes when all its squares are covered with no overlapping dominoes and no dominoes overhanging the board.

Proof using exhaustion

First, we will number the squares from 1 to 16.

Now, we can rotate the board if necessary to make the removed squares be 1 and 16. A domino must cover square 2.

If that domino is placed to cover squares 2 and 6, then the following domino placements are forced in succession: 5-9, 13-14, and 10-11, at which point there is no way to cover square 15.

Otherwise, a domino placed at 2-3 must cover square 2. Then the following domino placements are forced: 4-8, 11-12, 6-7, 5-9, and 10-14, and again there is no way to cover square 15.