|
Question:
Bend the Triominoes
A triomino is like a domino, but it covers three squares.
There are two different kinds of triominoes: straight ones and bent ones.
Suppose you have a square chessboard of size 2^n by 2^n.
Remove any square from the board, and prove that the
remaining squares can be covered by bent triominoes.
Answer:
The proof is by induction.
For the case n = 1 and n = 2, this can be done
without so much trouble, by trial and error.
Now I prove that 2^n by 2^n w/ a missing square
can be covered with bent triominoes w/ an assumption
that 2^(n-1) by 2^(n-1) missing a square can be so covered.
Divide this 2^n by 2^n square board into four squares
having size 2^(n-1) by 2^(n-1), separated by center vertical
lines and center horizontal lines, i.e. fit the cartesian
coordinate grid onto the square with origin at the center
of the square, as shown in the following ascii art:
-------------------------
| | |
| | . |
| II | I |
| | |
| | |
-------------------------
| | |
| | |
| III | IV |
| | |
| | |
-------------------------
Without a loss of generality, suppose that the square at first
quadrant of the board is removed, as indicated by the dot.
Then I carefully place a bent dominoe in the center so that it
removes one square from each of the II, III, and IV square boards
(at their corners). Now we have four 2^(n-1) by 2^(n-1) squares
each missing a square. By induction hypothesis, all four of
these can be covered, and hence 2^n by 2^n.
-- Henry K. Shin
|
