|
This problem is solved with "recursion".
Consider a square with 2^n cells on each side, one corner cell removed. Now, let us prove that it can be filled with triominos if we know for a fact that this can be done to a similar shape with 2^(n-1) on each side. Here's our smaller shape:
__
| |_
|____|
Since 2^n is twice as much as 2^(n-1), the smaller shape's side is 2 times less than the bigger shape. The big shape can be divided into four parts like this:
_________
| | |_
| A | B |
|-----+-----|
| C | D |
|_____|_____|
The area B will be the smaller shape, since it is a square with the side of 2^(n-1) with one cell removed from the corner. The other three areas, A, C and D can each fit the smaller shape, and still have one cell left over.
But in placing the smaller shape into the three areas, we can rotate them, so that their removed corner is in the center of the big shape. This will result in a triomino-shaped hole in the center of the big shape, which we can fill with one additional triomino piece.
Thus, we have shown that if the "imperfect square" of 2^(n-1) cells on each side can be tiled with triominos, one with 2^n sides can be as well. Since for n=1, the shape is a triomino piece, and therefore can be tiled, all natural values of n>1 will result in a "tilable" shape. |
This is a triomino piece:
