# Tiles: Induction

• Jun 2nd 2007, 10:11 PM
tukeywilliams
Tiles: Induction
I am trying to prove that a $\displaystyle 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 $\displaystyle n$. Base case: For $\displaystyle n = 1$, a $\displaystyle 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 $\displaystyle k$, a $\displaystyle 2^{k} \times 2^{k}$ square grid with any one square removed can be covered using $\displaystyle r$ L-shaped tiles, were $\displaystyle r$ is some positive integer. Then a $\displaystyle 2^{k+1} \times2^{k+1}$ board with one square removed can be covered by $\displaystyle 2r$ L-shaped tiles. Conclusion: Hence, by induction, for a positive integer $\displaystyle n$, a $\displaystyle 2^{n} \times 2^{n}$ square grid with any one square removed can be covered by $\displaystyle 2r$ L-shaped tiles. $\displaystyle \square$

Is this proof correct?

Thanks
• Jun 3rd 2007, 07:10 AM
ThePerfectHacker
We know we can over $\displaystyle 2^k \times 2^k$ board by the induction hypothesis.

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

4 smaller squares are $\displaystyle 2^k\times 2^k$. When we bring them together we get a $\displaystyle 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!
• Jun 3rd 2007, 07:56 AM
tukeywilliams
Just wondering, is my proof valid?
• Jun 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 $\displaystyle 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?
• Jun 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 $\displaystyle 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.
• Jun 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?
• Jun 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.
• Jun 6th 2007, 11:22 AM
tukeywilliams
Well we were supposed to prove that we could tile a $\displaystyle 2^{n} \times 2^{n}$ board with one square removed. Apparently we disproved this, and say that we can tile an entire $\displaystyle 2^{n} \times 2^{n}$ board given that we choose to remove the squares in a strategic fashion?
• Jun 6th 2007, 12:24 PM
ThePerfectHacker
Let me try again.

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

2)We want to show it for a $\displaystyle 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 $\displaystyle 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 $\displaystyle 2^{n+1}\times 2^{n+1}$ is tiled except for a single arbitrary selected tile.

14)Q.E.D.
• Jun 6th 2007, 12:33 PM
tukeywilliams
oh ok, this makes perfect sense now. Thats what I was thinking. Thanks