Can L-Shaped Tiles Fit Perfectly on a 2xn Board If n Is Not Divisible by 3?

[cocoabeens]

Say there's a 3 block/pixel/square shape in L- formation that can be rotated on a board of size 2 x n. G(n) is how many distinct ways the board can be tiled. I need to show that if n isn't divisible by 3, then G(n) is 0.

Given a block of three squares fitting on a board of size 2xn, and k blocks, if we assume G(n) =/= 0, then n is divisible by 3. We have that the board is established by a total of 3k squares of 2xn dimension. If G(n), the number of ways the board can be tiled, is not 0, (here's where I'm getting confused), select a nonzero value, say G(n)=2 (for n=3), n is divisible by 3. Is this it? Or do I show that if G(n) is =/=0, there is no way for it to be divisible by 3?
For the second part of this, I need to show that if n is divisible by 3, then G(n)= 2n/3, by first showing that G(n) = 2xG(n-3).
Is this one an induction proof? I'm a bit stuck on how to first show the G(n)=2xG(n-3) part...

Thanks so much in advance (Talking)

 

[Evgeny.Makarov]

Given a block of three squares fitting on a board of size 2xn, and k blocks, if we assume G(n) =/= 0, then n is divisible by 3.

Yes, this (the part after "if") is the contrapositive of the original claim.

We have that the board is established by a total of 3k squares of 2xn dimension. If G(n), the number of ways the board can be tiled, is not 0, (here's where I'm getting confused), select a nonzero value, say G(n)=2 (for n=3), n is divisible by 3. Is this it?

No, you need to prove the claim
\[
G(n)\ne0\implies 3\mid n
\]
for all $n$ and not just for $n=3$, As you said, $G(n)\ne0$ implies that the whole $2\times n$ board is covered by $k$ 3-square tiles, so $2n=3k$. Now use the Euclid's lemma.

For the second part of this, I need to show that if n is divisible by 3, then G(n)= 2n/3, by first showing that G(n) = 2xG(n-3).

Do you mean $G(n)=2^{n/3}$ instead of $G(n)=2n/3$?

To derive $G(n)=2^{n/3}$ from $G(n) = 2G(n-3)$, you also need the initial condition $G(3)=2$, which you have alredy shown.

Is this one an induction proof?

Showing $G(n) = 2G(n-3)$ does not require induction; using it to prove $G(n)=2^{n/3}$ does.

I'm a bit stuck on how to first show the G(n)=2xG(n-3) part...

Show that if the board is placed horizontally, then the leftmost L-shaped tile can be placed in two possible ways, and for each of those there is only one way to place the next tile. After that, the remaining board has size $2\times(n-3)$, and by definition it can be filled in $G(n-3)$ ways. Finally, use the rule of product.

To prove $G(n)=2^{n/3}$, proceed by induction in the usual way: form the induction statement $P(n)$, prove the base case, fix an arbitrary $k$, state the induction hypothesis for $k$ and use it to derive $P(k+1)$.

 

[cocoabeens]

Whoops, sorry yes, G(n)=2^(n/3).

So for the induction step, would it look like this-

base case: for n=3, 2^(n/3)=2*R(n-3)
left hand side: R(3)=2^(3/3) =2
right hand side: 2*R(3-3)=2 (r(0) must be 1?)

inductive hypothesis: for some k that is divisible by 3, G(k)=2^(k+3/3) =2*G(k) holds true ((k+3)/3) instead of ((k+1)/3) because we only deal with multiples of three).
is this set up right? or do i not involve the 2*G(n-3) bit into the inductive portion at all?

 

[Evgeny.Makarov]

So for the induction step, would it look like this-

base case: for n=3, 2^(n/3)=2*R(n-3)

What is R? And what exactly are you proving in the base case? I have already written an outline of a proof by induction, and the first step is to write the induction statement $P(n)$. It is usually obtained by removing "for all $n$" from the claim you need to prove. In this case, you need to prove that for all $n$ divisible by 3, $G(n)=2^{n/3}$. Thus, $P(n)$ is $G(n)=2^{n/3}$. For $n=3$, this becomes $G(3)=2$. It is this that you should be proving in the base case and not $2^{n/3}=2R(n-3)$. And you prove it by definition of $G$, not by the property $G(n)=2G(n-3)$ (unless you define $G(0)=1$, in which case the base case should be for $n=0$).

inductive hypothesis: for some k that is divisible by 3, G(k)=2^(k+3/3) =2*G(k) holds true

$G(k)=2G(k)$? I assume the left-hand side whould be $G(k+3)$. Do you mean $k+\frac{3}{3}$ (which is what $k+3/3$ means) or $\frac{k+3}{3}=(k+3)/3$? So, why does
\[
G(k+3)=2^{(k+3)/3}=2G(k)
\]
hold? The fact that $G(k+3)=2G(k)$ we have proved, by why does $G(k+3)=2^{(k+3)/3}$ hold? And where do you use the induction hypothesis?

This is all pretty close to the correct proof, of course, because the proof is quite simple, but it's all the more reason for writing everything clearly. I suggest studying the outline of an inductive proof in your textbook or https://driven2services.com/staging/mh/index.php?posts/45490/.

 

[blue_raver22]

Hello,

I would like to offer some clarification and guidance on your proof.

Firstly, the statement "if n isn't divisible by 3, then G(n) is 0" can be restated as the contrapositive statement "if G(n) is not equal to 0, then n is divisible by 3". This means that if there are any possible ways to tile the board, then the number of squares on the board (n) must be divisible by 3.

To prove this, we need to consider the dimensions of the board and the shape of the block being used. Since the block is in an L-formation, it takes up 3 squares on the board. Therefore, the total number of squares on the board (n) must be a multiple of 3 in order for the block to fit perfectly without any leftover squares. This is why if G(n) is not equal to 0, then n must be divisible by 3.

For the second part of your proof, you can use induction to show that if n is divisible by 3, then G(n) = 2n/3. Induction is a method of mathematical proof where you first prove the base case (in this case, when n = 3) and then show that if the statement holds for a certain value of n, it also holds for the next value (in this case, n + 3).

To prove the base case, you can use the fact that when n = 3, G(n) = 2. This is because with a board of size 2x3, there are only 2 ways to tile it with the L-shaped block.

Next, you can assume that the statement holds for n = k. This means that G(k) = 2k/3. Now, we need to show that if n = k+3, then G(n) = 2n/3.

Since n = k+3, we can write G(n) as G(k+3). Using the assumption that G(k) = 2k/3, we can rewrite this as G(k+3) = 2(k+3)/3. Simplifying this, we get G(n) = 2n/3, which is the statement we wanted to prove.

Therefore, using induction, we have shown that if n is divisible by 3, then