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