The Mathematical Garden

Mathematical Induction in action

Prove that given a 2ⁿ by 2ⁿ checkerboard with any one square deleted, it is possible to cover this board with L-shaped pieces.

Proof

1. Check the base case at n = 1. At n = 1, you get a 2 x 2 checkerboard, with one square removed.

2. Assume that the proposition is true for some integer k, that is,

   It is possible to cover any 2^k by 2^k board, with any 1 square missing, with L-shaped pieces.

Prove that it is possible to cover a 2^k+1 by 2^k+1 board.

A 2^k+1 by 2^k+1 checkerboard missing one square can be represented as the following,

Here is the trick. We divide dividing board into 4 smaller boards as follow and adding an L-shaped block to the middle.

Each smaller board has 2^k by 2^k squares. By the induction assumption, we know that a 2^k by 2^k checkerboard that is missing one square can be covered by L-shaped pieces.

Therefore the whole 2^k+1 by 2^k+1 checkerboard can also be covered.

By M.I., for every 2ⁿ by 2ⁿ checkerboard with any one square deleted, it is possible to cover this board with L-shaped pieces.

Exercise

Prove that every 2n by 2n (n > 1) chessboard can be tiled with T-ominos