Results 1 to 10 of 10

Math Help - Tiles: Induction

  1. #1
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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!
    Attached Thumbnails Attached Thumbnails Tiles: Induction-picture3.gif  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    Just wondering, is my proof valid?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tukeywilliams View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by tukeywilliams View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member tukeywilliams's Avatar
    Joined
    Mar 2007
    Posts
    307
    oh ok, this makes perfect sense now. Thats what I was thinking. Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Tiles
    Posted in the Statistics Forum
    Replies: 5
    Last Post: July 30th 2010, 01:32 PM
  2. arranging tiles..
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2010, 07:06 PM
  3. Algebra Tiles
    Posted in the Algebra Forum
    Replies: 1
    Last Post: November 7th 2009, 12:15 PM
  4. Town Hall Tiles
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 3rd 2009, 05:57 AM
  5. Rita's Tiles
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: December 15th 2008, 09:42 PM

Search Tags


/mathhelpforum @mathhelpforum