PROVEL that for every positive integer k, a (2^k) x (2^k) grid with one square r
ID: 2943565 • Letter: P
Question
PROVEL that for every positive integer k, a (2^k) x (2^k) grid with one square removed can be tiled by L-shaped 3-square tiles.Explanation / Answer
For m>0 Define an "L of size 2^m" to be a square of side length 2^m with a square of side length 2^(m-1) removed from the corner, so that the tiles of the given problem are Ls of size 2. Note that 4 Ls of size 2^m can be arranged* into an L of size 2^(m+1), so incuctively, we can tile an L of size 2^k for any k>0. Now let j be the smallest positive integer such that there exists a square of side length 2^j with one unit square removed that cannot be tiled (assuming, contrariwise, that such a j exists). The removed unit square must be in one of the 4 quadrants of the whole square. That quadrant (minus the removed unit square) can be tiled by the assumption of minimality of j. The remaining 3 quadrants form an L of size 2^j, and can also be tiled. Thus, the whole square (minus one unit square) can be tiled, a contradiction.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.