Tiles: Induction

Printable View

June 2nd 2007, 10:11 PM
tukeywilliams

Tiles: Induction

I am trying to prove that a $2^{n} \times 2^{n}$ board with one square removed can be covered by L-shaped tiles(3 square L-shaped tile). Here is my proof:

20. Proof: We use induction on $n$ . Base case: For $n = 1$ , a $2 \times 2$ square grid with any one square removed can be covered by exactly one L-shaped tile. Induction step: Suppose now as induction hypothesis that for some positive integer $k$ , a $2^{k} \times 2^{k}$ square grid with any one square removed can be covered using $r$ L-shaped tiles, were $r$ is some positive integer. Then a $2^{k+1} \times2^{k+1}$ board with one square removed can be covered by $2r$ L-shaped tiles. Conclusion: Hence, by induction, for a positive integer $n$ , a $2^{n} \times 2^{n}$ square grid with any one square removed can be covered by $2r$ L-shaped tiles. $\square$

Is this proof correct?

Thanks
June 3rd 2007, 07:10 AM
ThePerfectHacker

1 Attachment(s)

We know we can over $2^k \times 2^k$ board by the induction hypothesis.

To cover a $2^{k+1}\times 2^{k+1}$ board we build one as follows. (See below).

4 smaller squares are $2^k\times 2^k$ . When we bring them together we get a $2^{k+1}\times 2^{k+1}$ big square. Now we ask, "is it possible oto tile this big square"? And the answer is, yes! But how do we show it? The small red square represents a missing peice in this big square. WLOG we will assume it is in the upper left square. Now by the induction hypothesis we can tile the lower left, upper right, lower right squares with one tile removed. But not just any tile, we pick a tile that meets in the center, shown by blue squares. Now, we can tile the LL,UR,LR square because one tile is removed. We can tile the UL square because only one tile is removed by induction hypothesis. And we can tile the middle blue square because they are arranged in a shape of a tromino. Thus, we can tile the entire thing!
June 3rd 2007, 07:56 AM
tukeywilliams

Just wondering, is my proof valid?
June 6th 2007, 12:59 AM
tukeywilliams

Quote:

We can tile the UL square because only one tile is removed by induction hypothesis. And we can tile the middle blue square because they are arranged in a shape of a tromino. Thus, we can tile the entire thing!

I am not sure that I understand this. How can we tile the UL square if it is the one removed? Did you mean can't? What middle blue square are you talking about? We can't tile the entire thing right. We can only tile a $2^{k+1} \times 2^{k+1}$ board with one square removed right? Wouldn't the proof of the inductive step end after choosing the blue squares at the centers and knowing that we can tile them by the induction hypothesis? Thus we can tile 3 out of the 4 squares as required?
June 6th 2007, 06:46 AM
ThePerfectHacker

Quote:

Originally Posted by tukeywilliams

I am not sure that I understand this. How can we tile the UL square if it is the one removed?

The 4 smaller squares: Upper left, Upper right, Lower left, Lower right. Are all $2^k \times 2^k$ squares. So by induction no matter what tile is missing we can tile them. So the UL has an arbitrary tile is removed. And the other square we porpusely removed the tridonomino in the middle. So we can tile it with a single tridonomino.
June 6th 2007, 11:05 AM
tukeywilliams

yes but does this imply that we can tile the entire all at once? We can only tile it if one square is removed. But separately we can tile the whole thing?
June 6th 2007, 11:13 AM
ThePerfectHacker

Quote:

Originally Posted by tukeywilliams

yes but does this imply that we can tile the entire all at once?

Correct. But we pick 3 square so that their tiles appear at a corner. So that we can cover everyhitng.

---
What is your problem? You do not understand.
June 6th 2007, 11:22 AM
tukeywilliams

Well we were supposed to prove that we could tile a $2^{n} \times 2^{n}$ board with one square removed. Apparently we disproved this, and say that we can tile an entire $2^{n} \times 2^{n}$ board given that we choose to remove the squares in a strategic fashion?
June 6th 2007, 12:24 PM
ThePerfectHacker

Let me try again.

1)By hypothesis we assume we can tile a $2^n\times 2^n$ square with one tile missing.

2)We want to show it for a $2^{n+1}\times 2^{n+1}$ square with a tile missing.

3)We will show number #2 in order to use induction.

4)So pick any tile you want and remove it.

5)Now divide this square into 4 $2^n\times 2^n$ smaller squares.

6)He know has 4 subsquares: Upper Left, Upper Right, Lower Left, Lower Right.

7)WLOG we can say the removed tile in #4 is located in to Upper Left subsquare (The blue one).

8)Remove the tile corners meeting in the center of the Upper Right, Lower Left, Lower Right squares. (The red ones).

9)Now You can tile the Upper Left without the tile (blue) by hypothesis.

10)You can tile the remaining subsquares without the red tiles by hypothesis.

11)Now you have tiled everything except the triple (red L) in the center and blue square.

12)You can cover those three with a tronimo.

13)So now the entire $2^{n+1}\times 2^{n+1}$ is tiled except for a single arbitrary selected tile.

14)Q.E.D.
June 6th 2007, 12:33 PM
tukeywilliams

oh ok, this makes perfect sense now. Thats what I was thinking. Thanks