This is a triomino piece:
(A 2 x 2 cell square with one of the corner cells removed)

Prove that a square, 2^n cells to the side, with one square cell removed from the corner can be covered with triomino pieces without any overlapping or going over the border for any natural value of n. The triominos can be rotated.

(For example if n = 1, the result is a triomino shape to begin with - a 2 x 2 square with one cell removed.)

Inductive proof:

Clearly this holds for N=1 (by using one Triomino).  We will now show that if it holds for N, it holds for N+1.

The N+1 case is, of course, twice as big as the N case, in each direction.  Take our solution for the N case, and use it to cover the lower-right quadrant of the N+1 case.  It will fill it in perfectly.  Now we are left with a six-sided figure -- the other three quadrants, each of which is a perfect (and complete!) square of 2^N size.  Put another copy of our solution for the N case on the top-left quadrant, which leaves the lower-right cell of that quadrant empty.  Rotate our solution for the N case counter-clockwise by 90 degrees, and put the result into the lower-left quadrant, which leaves the upper-right cell of that quadrant empty.  Rotate the original solution for the N case clockwise by 90 degrees, and put that result into the upper-right quadrant, which leaves the lower-left cell of that quadrant empty.  Now, one more single Triomino can cover the three cells we left empty -- the lower-right cell of the upper-left quadrant, the upper-right cell of the lower-left quadrant, and the lower-left cell of the upper-right quadrant.

Posted by Caleb on 2012-08-26 17:59:14