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

[GregA]

I have to prove that for any integer n a $$2^n x 2^n$$ 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?

 

[AKG]

No need to prove by contradiction:

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

where k is such that (3+1)ⁿ = 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:

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

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

so 4ⁿ - 1 is a multiple of 3, and 4ⁿ - 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 2ⁿ⁺¹ x 2ⁿ⁺¹ board is like four 2ⁿ x 2ⁿ boards. If you original 2ⁿ⁺¹ x 2ⁿ⁺¹ has one of the squares removed, then you're left with four 2ⁿ x 2ⁿ 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 2ⁿ x 2ⁿ 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?

 

[Gokul43201]

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 :

(3+1)^n = 3k + 1, and such a k exists by the binomial theorem, plus the fact that 3 is prime.

Why do you need 3 to be prime ?

 

[GregA]

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

The goal I'm after is that if there is a $$2^{2(n+1)} - 1$$ board then it can be represented as 4 $$2^{2n} - 1$$ 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
$$2^{k+1}$$ x $$2^{k+1} - 1 =$$
$$4(2^k$$ x $$2^k) - 1 =$$
$$4(2^{2k} -1) +3$$ which is what I set out to prove

is this any better?

 

[AKG]

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.

 

[AKG]

GregA, your recent post (post #4 of this thread) doesn't make any sense.

 

[Gokul43201]

GregA, your recent post (post #4 of this thread) doesn't make any sense.

He's proving the divisibility by Induction. It looks okay. But, as far as this problem is concerned, it is unnecessary.

 

[Gokul43201]

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]

 

[GregA]

GregA, your recent post (post #4 of this thread) doesn't make any sense.

unfortunately for me that's not surprising

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 ...

 

[Nimz]

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?

 

[GregA]

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 $$2^k$$ x $$2^k -1$$ board be tileable for all k
If this is true then it is tileable for k+1

2) $$2^{k+1}$$ x $$2^{k+1} - 1 = 4(2^{2k} - 1)$$
$$4(2^{2k} - 1) = 3(2^{2k}) + (2^{2k} - 1)$$

3) Now we know that the $$(2^{2k} - 1)$$ 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 $$(2^{2k})$$ in size.
$$3(2^{2k}) = 3(2^{2k}-1) +3$$ 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
$$(2^{2(k-1)} - 1)$$ board that has been proven to have been made up of $$4(2^{2k} - 1)$$ 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?

 

[Gokul43201]

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

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.

1) 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

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.

2) $$2^{k+1}$$ x $$2^{k+1} - 1 = 4(2^{2k} - 1)$$
$$4(2^{2k} - 1) = 3(2^{2k}) + (2^{2k} - 1)$$

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.

3) Now we know that the $$(2^{2k} - 1)$$ board is tileable.

Correct.

Let there be four quadrants in a 2x2 arrangement,

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.

and that this board occupies the top right quadrant,

This statement can be made without loss of generality.

let the missing tile also be at the top right.

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.

4) The three boards remaining are $$(2^{2k})$$ in size.
$$3(2^{2k}) = 3(2^{2k}-1) +3$$ so we have another 3 boards that we know are tileable, but we have 3 holes remaining.

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).

Let each each 3 boards occupy one quadrant each, 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
$$(2^{2(k-1)} - 1)$$ board that has been proven to have been made up of $$4(2^{2k} - 1)$$ boards with an additional L shaped tile at the centre.

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."

 

[GregA]

Thanks for the reply Gokul ...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 )
$$4(2^{2k} - 1) = 3(2^{2k}) + (2^{2k} - 1)$$ I should have -3 on the RHS

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:

 

[AKG]

I don't think you should be doing any calculations for this problem. The fact that 4(2^2k-1) = 3(2^2k) + (2^2k-1) - 3 is irrelevant.