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.)

(In a recursive proof, you prove that if it is true for n, then it is true for n+1 and show imperically that it is true for n=1)

Part A: prove the recursive element.

Step 1: A square 2^(n+1)on the side can be considered to be 4 squares of side 2^n:


  
  


  
  


Step 2. For three of these squares, fill it with triominoes, so that the empty space is the one closest to the center:



 




Step 3. A triomino wil cover those three spaces:



XX
X




Step 4. Now fill in the fourth square with the empty spot in the far corner:




XX
XOOOO
OOOO
OOOO
OOO

Thus it is true that if for any value of a, you can tile the square minus a corner, it is true for 2a, and specifically, if it is true for a=2^n, then it is true for a=2^(n+1).

Part B: Show it to be true fo the lowest non-trivial value of n:

For n=1 it is self-evident. The pattern for n=2 is:


XX
xOO
O

Which is basically the same pattern used in the recurssion.

Posted by TomM on 2002-05-21 19:00:07