4
$\begingroup$

There is a room of dimension $2\times 12$ units. You have to tile it. There are two types of tiles:

  • I-Shaped - it is of a dimension $1\times 2$ units,
  • L-Shaped - it is in the shape of $L$ which has an area of $3$ sq. units.

enter image description here

In how many ways can you tile it?

I have studied some basics of permutation and combination but I can't use it in the this question.

Note:

  • The $I$ shaped tiles are identical from both sides.
  • You can rotate the tiles in any direction if it will fit.
  • You have an unlimited supply of tiles.
$\endgroup$
  • $\begingroup$ What have you tried so far? $\endgroup$ – Vinyl_cape_jawa Feb 23 at 15:05
  • $\begingroup$ I couldn't come to any solution $\endgroup$ – Abhinav Feb 23 at 15:08
  • $\begingroup$ I don't know how to start $\endgroup$ – Abhinav Feb 23 at 15:08
  • $\begingroup$ Maybe you can try doing this recursively, like A[12]=A[11]+A[9], and I think you need a B to tell about if one block is stuck out, like this(can anyone tell me how to change the line please) $\endgroup$ – Math Lover Feb 23 at 15:09
  • $\begingroup$ The area you need to tile is not big at all, try out some $\endgroup$ – Vinyl_cape_jawa Feb 23 at 15:09
1
$\begingroup$

I am not quite sure if you can use basic permutation/combination to solve this problem.

But It can be approached recursively.

Denote the number of ways of tiling a $2\times n$ area by given tiles as $T(n)$, and the number of ways of tiling a $2 \times n$ area plus a leading block on top or bottom as $S(n)$

Then,

$T(n)=T(n-1)+T(n-2)+ 2S(n-2)$

$S(n)=S(n-1)+T(n-1)$

Take the first relation for example. If you lay the first tile as 'I' and vertically, you result in a $2\times (n-1)$ area. If you lay the first tile 'I' horizontally, you will have to cover the area below it with another horizontal 'I' to cover fully, you get a $2\times (n-2)$ area. If you lay a 'L', you can do it in two valid way, and by symmetry, they have same number ways of being tiled, names $S(n-2)$.

By solving the recurrence relation, you can get the answer to $T(12)$, i.e., your question.

$\endgroup$
1
$\begingroup$

HINTS:

Since the are you need to tile is not that big at all you could easily just list all the tilings (which is definitely not a pretty way to solve it but if you have no idea how to start it at least gives you a starting point).

Using an odd number of $L$ shaped tile you won´t succeed so you can directly start checking the cases where you have an even number of $L$ tiles.

Using $0$ of the $L$ tiles you will be able to tile it using only the $I$ shaped ones and this can be done in only $1$ way.

Using $2$ of the $L$ shaped ones you have $4$ cases,

1) they are next to each other

2) they have $2$ of the $I$ shaped ones inbetween them

3) they have $4$ of the $I$ shaped ones inbetween them

4) they have $6$ of the $I$ shaped ones inbetween them

Observe that in each of these cases you get a factor of $2$ in the number of solutions since each of these can be flipped around a horisontal axis.

And so on...

As I said this is definitely not a nice solution, creating a recurrence relation is a lot nicer altough I am unsure if you know how to use recurrence relation to solve this. Please let me know if you do, in that case we could work out something more mathematical :)

Hope this helped.

$\endgroup$
  • $\begingroup$ I have another idea. Can we make groups of 2*2 boxes with 2 I-shaped tiles. By P&C we can make that total number of combinations would be $2^6$.Similarly for 3*2 box and so on. After we complete upto 6*2 box we can add the earlier combinations. $\endgroup$ – Abhinav Feb 23 at 16:12
1
$\begingroup$

Let $A_n,B_n,C_n,D_n$ denote the following four shapes, where $n$ is the width of the shape. Let $a_n,b_n,c_n,d_n$ be the number of ways to tile them, respectively.

enter image description here

The top right field of $A_n$ can be covered by a vertical $I$, by a horizontal $I$, by the apex of an $L$, or by the "toe" of an $L$. Removing this tile produces either the shape $A_{n-1}$, $D_n$, $B_{n-1}$, or $C_{n-1}$, respectively. We conclude $$\tag1a_n=a_{n-1}+d_n+b_{n-1}+c_{n-1}.$$ The rightmost field of $B_n$ can be covered by a horizontal $I$ or by the "toe" of an $L$. Removing this tile produces either $C_{n-1}$ or $A_{n-2}$, respectively. We conclude $$\tag2b_n=c_{n-1}+a_{n-2}.$$ The rightmost field of $D_n$ can only be covered by a horizontal $I$. We conclude $$\tag3d_n=a_{n-2}.$$ And by symmetry, we clearly have $$ \tag4c_n=b_n.$$ Using $(3)$ and $(4)$ to eliminate $c_n$ and $d_n$, we find $$ a_n=a_{n-1}+a_{n-2}+2b_{n-1}$$ and $$a_{n+1}=a_n+a_{n-1}+2b_n=a_n+a_{n-1}+2(b_{n-1}+a_{n-2})$$ and from these eliminate $b_{n-1}$: $$a_{n+1}= 2a_n+a_{n-2}.$$ This recursion is good enough to quickly compute the desired value $a_{12}$ by hand from the readily obtained starting values $$a_0=1, \quad a_1=1, \quad a_2=2.$$ (The recursion can also be used to ultimately obtain an explicit formula for $a_n$ for arbitrary $n$)

$\endgroup$
0
$\begingroup$

Here is a combinatorial proof of the following recurrence mentioned at the end of Hagen von Eitzen's answer. $$ a_n=2a_{n-1}+a_{n-3} $$ To specify a tiling of a $2\times n$ rectangle, start with a tiling of a $2\times (n-1)$ board, add a vertical $I$ tile to the left end, then do one of two things:

  • Leave it as is.

  • Make whichever of the below replacements is possible, where the xs mark the $I$ tile at the left end.

X Y    ->  X X
X Y        Y Y

X L L  -> L X X
X L       L L

X L    -> L L
X L L     L X X

X Y Y  -> L M M
X Z Z     L L M

This generates almost all possible $2\times n$ tilings. The only ones remaining are the ones ending in

L L M
L M M,

which are accounted for by the $a_{n-3}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.