Tiling With Trominoes

Tiling with trominoes Given a 2 n × 2 n (n > 0) chessboard , with one corner square removed, prove that it can be tiled with trominoes. (A tromino is a figure that can exactly cover 3 contiguous squares, not all in the same rank or file.) Proof. The statement is true for n = 1, when a single tromino covers a 2 × 2 chessboard with a corner square removed. Suppose the statement is true for n. Given a 2 n +1 × 2 n +1 chessboard with a corner square removed, partition it into 4 2 n × 2 n chessboards A, B, C, and D, one of which (A) has the corner square removed. Place one tromino T in the center of the chessboard so that one square is in each of chessboard B, C, and D. Then apply case n to tile A, B\T, C\T, and D\T. These 4 tilings together with T form a tiling of the 2 n +1 × 2 n +1 chessboard. (Diagram below shows the case n = 2.)

B

C T

A

D