1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Another proof: Do I still have more work to do?

  1. Apr 21, 2006 #1
    I have to prove that for any integer n a [tex] 2^n x 2^n [/tex] grid with one square remove can be covered with L shaped tiles made up of 3 squares.

    I can prove by contradiction that the number of tiles available to use is always a multiple of 3 but doing this doesn't prove that it works for L shaped tiles.

    The best I can do so far is give is a set of instructions that define how you can always cover the grid with L shaped tiles:

    0) get 4 square tiles and arrange them in a 2x2 square...remove one of the tiles.
    1) Rename this tile as 'K' and place it with the hole at the top right
    2) Place a similar tile above the first and rotate it 90 degs clockwise
    3) Place a similar tile to the right of the first tile and rotate it 90 degs anticlockwise
    4) Place a final similar tile diagonally opposite the first with no rotation
    5) Plug the hole in the middle with a 3 square tile
    6) Call this tile K + 1 and then proceed to step 1

    Does this count as proof by induction?
    Last edited: Apr 21, 2006
  2. jcsd
  3. Apr 21, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    No need to prove by contradiction:

    2n x 2n - 1
    = (2n)² - 1
    = 22n - 1
    = (2²)n) - 1
    = 4n - 1
    = (3+1)n - 1
    = 3k + 1 - 1
    = 3k

    where k is such that (3+1)n = 3k + 1, and such a k exists by the binomial theorem, plus the fact that 3 is prime. Alternatively, you could have used modulo 3 arithmetic, and work with:

    4n - 1 = 1n - 1 (mod 3) since 4 = 1 (mod 3)

    So 4n - 1 = 1n - 1 = 1 - 1 = 0 (mod 3)

    so 4n - 1 is a multiple of 3, and 4n - 1 is exactly the number of tiles.

    Anyways, this isn't really relevant, since you can prove by induction that you can cover the board without having to first prove that the number of squares is a multiple of 3. The proof is simple.

    Hint: A 2n+1 x 2n+1 board is like four 2n x 2n boards. If you original 2n+1 x 2n+1 has one of the squares removed, then you're left with four 2n x 2n boards, with ONE of those smaller boards having one square removed. In order to use induction, you need to find a way to make it so that the other THREE smaller boards are like 2n x 2n boards, each with one square removed. Given that you're working with L-shaped pieces which cover THREE squares each, can you think of a way to do this?
  4. Apr 21, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I didn't understand AKG's hint, so here's another one (or maybe I'm doing the same thing he is) ...

    1. Assume you can tile a 2^n X 2^n board with a missing tile anywhere on the board.
    2. Then you can certainly tile a 2^n X 2^n board with a missing tile at one corner of the board.
    3. You have 3 more such boards (as explained by AKG), one of which is missing a tile...take it from here (it's similar to what you are doing with the 2 X 2 grids).

    PS :
    Why do you need 3 to be prime ?
    Last edited: Apr 21, 2006
  5. Apr 21, 2006 #4
    Thanks for the reply folks...I'm a real beginner with this sort of thing (number theory and proof writing etc...) and find it incredibly difficult to write out in legible terms what I have in my head :frown:

    The goal I'm after is that if there is a [tex] 2^{2(n+1)} - 1 [/tex] board then it can be represented as 4 [tex] 2^{2n} - 1 [/tex] boards with 3 tiles added to it to plug the gap in the centre.

    Base: if n=2 then 4*4 -1 = 4(4-1) +3
    If it works when n = k then it works if n = k+1
    [tex] 2^{k+1}[/tex] x [tex]2^{k+1} - 1 = [/tex]
    [tex]4(2^k[/tex] x [tex] 2^k) - 1 = [/tex]
    [tex]4(2^{2k} -1) +3[/tex] which is what I set out to prove

    is this any better? :redface:
    Last edited: Apr 21, 2006
  6. Apr 21, 2006 #5


    User Avatar
    Science Advisor
    Homework Helper

    You don't need 3 to be prime, my mistake.

    Anyways, see the attached image:

    STEP 1: You start with big board with one square removed
    STEP 2: You quarter the board into four smaller boards
    STEP 3: Pretend those three squares coloured in grey are removed.
    STEP 4: You know have one small board with one square missing, and three small boards for which you are pretending that one square is missing. Assume inductively that you can cover each of these boards (that's what the orange is).
    STEP 5: Cover the grey squares with one L-shaped piece. Those three grey squares were chosen so that they could be covered perfectly with one L-shaped piece. Now you've covered the whole original board.

    Attached Files:

  7. Apr 21, 2006 #6


    User Avatar
    Science Advisor
    Homework Helper

    GregA, your recent post (post #4 of this thread) doesn't make any sense.
  8. Apr 21, 2006 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    He's proving the divisibility by Induction. It looks okay. But, as far as this problem is concerned, it is unnecessary.
  9. Apr 21, 2006 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    GregA, use the standard induction steps for the problem :

    Step 1. When n=1, you have a 2 X 2 board. Removing one tile from this leaves an 3-tiled L. So, the trivial case works.

    Step 2. Assume a 2^n X 2^n board with a missing square can be completely tiled.

    Step 3. Given [2], you must show that a 2^(n+1) X 2^(n+1) board with a missing tile can be completely tiled.
    (i) Cut this board into 4 part;
    (ii) Each part is now a 2^n by 2^n board;
    (iii) One of these boards has the missing piece;
    (iv) Consider the 3 remaining boards;
    (v) Using knowledge from [2] and a little extra work, show that these 3 boards can be completely tiled; - that's for you to do
    (vi) The 4th board with the missing piece can be tiled by the assumption in [2]
  10. Apr 21, 2006 #9
    unfortunately for me thats not surprising :frown:

    The base is n = 1.. this gives us 2*2 - 1, a 3 square tile

    Let a 2^k x 2^k - 1 board be tileable for all k
    If this is true then it is tileable for k+1

    2^{k+1} x 2^{k+1} - 1 = 4(2^{2k} - 1)
    4(2^{2k} - 1) = 3(2^{2k}) + (2^{2k} - 1)
    now we know that (2^{2k} - 1) is tileable

    as for the other 3 boards...they can all be considered as (2^{2k} - 1) boards...
    These can be rotated such that their holes meet at one point (the interior corner of a larger L shape)...and this leaves a 3 square L shaped hole.

    Once plugged with a 3 square L tile you are left with a solid 2^{k+1} x 2^{k+1} board, on which a piece is missing.

    I really apologise folks...Its not so much figuring out how this is all true that is killing me, more its that I'm having real problems writing it mathematically that the 3 other boards can be tiled without resorting to explaining how in physical terms ...:frown:
    Last edited: Apr 21, 2006
  11. Apr 22, 2006 #10
    You have the right ideas for a proof by induction all in your first post. Reread Gokul's last post (especially (i) - (vi)). There the induction is set up for you. You just need to flesh out the details.

    The other three boards cannot be tiled if you considered them alone. But if you removed a particular square from each of them, now can you tile them? Look at the induction hypothesis. Since you removed extra squares, you have to fill them in again. Can you guarantee they can be filled in with L-shaped tiles?
  12. Apr 22, 2006 #11
    Thanks for all your replies and help...after having a bit of sleep I'm ready to try again...

    The base is n = 1.. this gives us 2*2 - 1, a 3 square tile

    1) Let a [tex] 2^k [/tex] x [tex] 2^k -1 [/tex] board be tileable for all k
    If this is true then it is tileable for k+1

    2) [tex]2^{k+1}[/tex] x [tex]2^{k+1} - 1 = 4(2^{2k} - 1)[/tex]
    [tex]4(2^{2k} - 1) = 3(2^{2k}) + (2^{2k} - 1) [/tex]

    3) Now we know that the [tex] (2^{2k} - 1) [/tex] board is tileable.
    Let there be four quadrants in a 2x2 array, and for whatever quadrant we choose to let this board reside in...we make sure that the 'hole' at one corner occupies the same position on the board as the board does with the array.

    4) The three boards remaining are [tex](2^{2k})[/tex] in size.
    [tex]3(2^{2k}) = 3(2^{2k}-1) +3[/tex] so we have another 3 boards that we know are tileable, but each has a hole missing.
    Let each each 3 boards occupy one of the remaining quadrants, and their missing tiles be positioned on its board opposite to the location of its quadrant.
    This ensures that there are 3 gaps at the centre.

    5) Finally due to the fact that the quadrants are in a 2x2 arrangement it folows that only 2 missing tiles at the centre can be on the same axis such that one must be above (or to the right of) the other 2...and as they all meet this fits the requirement for a 3 square L shaped tile.

    As we now have 3 tileable boards, each sharing one 3 square L shaped tile and one additional board with its hole missing. we have now have a
    [tex] (2^{2(k-1)} - 1) [/tex] board that has been proven to have been made up of [tex] 4(2^{2k} - 1) [/tex] boards with an additional L shaped tile at the centre.

    I know that the above is a bit longwinded and I probably lack some of the vocabulary to make it simpler but is this any better?
    Last edited: Apr 22, 2006
  13. Apr 22, 2006 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What's important is not the number of tiles but the fact that the region can be covered will the L-shaped tiles. In the case of n=1, you have a single L-shaped space after removing any 1 suare from the 2 X 2 grid. Hence, the n=1 grid can be successfully tiled.

    The first assumption is a correct step. The statement following that assumption is a statement you are not allowed to make yet. How can you say that it is also tileable for k+1, unless you've proved it. But you have not proved it...so don't say it yet.

    There's an error in where you're closing your parantheses. In the first line, the LHS is odd but the RHS is even. Anyway, what are you trying to show here ? Just by showing that two different shapes have the same number of tiles doesn't prove that they are the same shape - only that they have the same area.

    What you want to prove here is that a 2^(k+1) X 2^(k+1) board is made up of 4 2^k X 2^k boards. This is done simply by noting that quartering a square board results in 4 square pieces, each with half the side of the original square. Nothing much more leaborate than that is required. The final bit here is to note that there must now be a missing tile in one of the 4 smaller boards.

    The 4 smaller 2^k X 2^k boards can be arranged to make the bigger board only by arranging them in a 2X2 grid. You needn't assume something that has to be true.
    This statement can be made without loss of generality.
    This assumption is illegal, and unnecessary. It is illegal because you are required to prove something no matter what the position of that tile. And it is unnecessary because it doesn't affect what you are now goingto do with the other 3 boards.

    This doesn't mean that each board has one hole missing. Further, you don't even have to do this calculation. All you need to say is : "The 3 remaining boards are complete 2^k X 2^k boards. We know (from [2]) that we can tile a 2^k X 2^k board if there is a missing square anywhere on the board. So, we tile these 3 boards in a manner that leaves the missing square at a corner. We now rotate these 3 boards till the 3 untiled squares occupy 3 of the 4 neighboring squares of the central node (or vertex, defined as the intersection of 2 lines) of the bigger board. These 3 tiles, hence, form an L-shape that can be filled by another single L-tile. The 2^(k+1) X 2^(k+1) board has now been tiled, leaving one square vacant. (ie : P(k+1) has been proven to be true if P(k) is true).

    This is okay too, if perhaps, a little excessively descriptive.

    But you need to made a final closing statement - the point of the induction method. So far, you've only proved that the bigger board can be tiled assuming the smaller board can be tiled, so you need to finish with something like :

    "Thus, by induction, it follows that any board of size 2^n X 2^n with one missing tile anywhere on it can be covered with L-shaped 3-square tiles."
    Last edited: Apr 22, 2006
  14. Apr 22, 2006 #13
    Thanks for the reply Gokul :smile: ...the initial assumption with K+1 is a mistake I will make sure I don't make again.

    I made some edits to my post before seeing your post and one of them corrected the absolute position of my first board. (I should have removed the restriction on the missing tile location because I'm not asked to prove that it is tileable if the hole exist in a particular location :redface: )
    [tex]4(2^{2k} - 1) = 3(2^{2k}) + (2^{2k} - 1) [/tex] I should have -3 on the RHS :redface:

    But overall I really have a lot of work to do on making sure I filter out the all the junk from my arguments whilst making sure that what I leave behind covers every angle efficiently. :grumpy:
    Last edited: Apr 22, 2006
  15. Apr 22, 2006 #14


    User Avatar
    Science Advisor
    Homework Helper

    I don't think you should be doing any calculations for this problem. The fact that 4(22k-1) = 3(22k) + (22k-1) - 3 is irrelevant.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Another proof still Date
Yet another vector proof Oct 20, 2012
Another vector proof Oct 20, 2012
Another proof Sep 18, 2009
Another proof: x^2 + xy +y^2 > 0 Sep 17, 2009
Another epsilon-delta proof. Oct 18, 2007