help please!?

Question

How do we prove that, for a positive integer n, a 2^n x 2^n square grid with any one square removed can be coverd using L-shaped tiles of the following shape
_
l_l_
l_l_l

Answer 1

By mathematical induction.

We'll assume that for each n, the upper right tile is always the one that's removed.

For n=1, you have a 2x2 grid, so you can cover it with one L, like the one you just showed.

Now, suppose n>1. We assume that we are able to cover a 2^n x 2^n grid with L's, with the upper right square removed. Then, we show how to cover a 2^(n+1) x 2^(n+1) grid with L's, again with the upper right square removed.

Divide the 2^(n+1) x 2^(n+1) grid into four equal-sized grids. They have size 2^n x 2^n, and can be covered with L's with the upper right square removed. Now, take the upper left and lower right subgrids and rotate them, so that 3 of the missing squares form an L. You can fill in an L in that empty space, and you have your covering. Try it for the case n=1 to n=2, for instance, and you'll see what I mean.

By the principle of mathematical induction, since it's true for n=1, and its truth for any n implies its truth for n+1, the statement is true for all n (that a covering is possible).

Answer 2

For the case n = 1, it's trivially true. For the case n = 2, break the grid up into 4 quadrants and show that, with the 'upper right' square missing, the remaining 15 squares can be 'covered' by 5 tiles (Hint: treat the upper right quadrant as an area covered by one tile so that any of the 4 squares in the quadrant can be left 'uncovered' by simply rotating the tile) Show that the remaining 12 squares can be covered exactly by 4 tiles. (You may have to 'fool around' with this for a bit to see how they 'interlock' to cover the 12 squares that are arranged in an 'L' shape, but it's fairly straightforward) Once you have this, any square in the grid can be left 'uncovered' by symmetry.

Now, for the case n = 3, break the grid up again into 'quadrants' that are 8 X 8 squares in size. Now show how the region consisting of the other 63 squares can be covered by 21 of the 'L' tiles (again, a bit of 'fooling around' will give it to you) and again, by symmetry, you'll see that you can leave 'uncovered' ang square in the first quadrant so, by symmetry, you can uncover any grid in the entire 8 X 8 array.

You should also notice a 'pattern' tothe way the 'L' tiles are arranged. Once you have that, proceed by induction to prove it for all n ☺

It's an hour or so of work. But HEY!! If it was easy, any fool could do it ☺


Doug

Answer 3

This is a little hard to follow so I suggest you draw an 8 x 8 chess board, color a square black and try to follow the arguments on that picture. The proof is done by induction. For n=1, it is obvious, what you are given is the rest of the 2 x 2 chess board. Now assume for n, show for n+1. Given a 2^(n+1) x 2^(n+1) chess board, divide it into 4 quadrants each, with one of them containing the square missing. Now those quadrants are of size 2^n x 2^n and the quadrant with the missing point can be covered with your L shapes by the inductive hypothesis. Now you remove one square from each of the other quadrants at the point where they touch (center). Then each such quadrant minus one point is also covered by L shapes again by inductive hypothesis and the missing squares at the center is also of the L shape so you are done.

Answer 4

by defective chess board algorithm.