Mathematical Induction in action
Prove that given a 2n by 2n checkerboard
with any one square deleted, it is possible to cover this board
with L-shaped pieces.
Proof
Check the base case at n = 1. At n = 1, you get a 2 x 2
checkerboard, with one square removed.
Assume that the proposition is true for some integer k, that is,
- It is possible to cover any 2k by 2k board, with
any 1 square missing, with L-shaped pieces.
Prove that it is possible to cover a 2k+1 by 2k+1 board.
A 2k+1 by 2k+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 2k by 2k squares. By the induction
assumption, we know that a 2k by 2k checkerboard that is
missing one square can be covered by L-shaped pieces.
Therefore the whole 2k+1 by 2k+1 checkerboard can also
be covered.
By M.I., for every 2n by 2n 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
|