39i just gave the start dude, for others tot ry:)
What is the number of ways to tile a 9x3 floor using 3x1 tiles ?
(This requires recursion)
I am explaining the question a bit more elaborately with some examples.. because you may not have understood tiling... :)
The example below shows a floor of size 9x3 tiled using black tile (of size 3x1)
These are some ways..
-
UP 0 DOWN 0 1 37
37 Answers
1it should be (3/2)^9
ie. 38 approximately
if we see this case as a case of recursion then
F(n) <= (3/2)^n
n=9 here
so
f(n)<=(3/2)^9
62no arshad... there is a better way to solve.. read b555's post no 13 and try to use that...
1Well, actually I don't have an elegant solution for this question.
How I proceeded is-
1) No Horizontal tiles- 1 way
2) All Horizontal tiles- 1 way
3) Three Horizontal tiles- 7 way
4) Six Horizontal tiles- 5c3
Total- 19 ways.
39it has stayed unsolved for long enough, so i don want to leave it like this anymore...
here is the general solution:
Let us compute, in general, the number xn of ways to tile a n x 3 floor with 3x1 tiles.
If the first tile (occupying the top-left corner) is horizontal, we are left to tile a
(n-1) x 3 floor, in xn-1 ways.
If the first tile (occupying the top-left corner) is vertical, we cannot avoid using two more vertical tiles adjacently to it,
so we are left to tile a (n-3) x 3 floor, in xn-3ways.
The first values are easily computed: x1=1 ,x2=1 ,x3=2 .
for n≥4, we have the recurrence relation
xn =xn-1+xn-3
You need know how to solve such a linear relation: consider its characteristic polynomial λ3-λ2-1=0, for distinct roots λ1,λ2,λ3(one real, two complex).
then xn=aλ1n+bλ2n+cλ3n
where a,b,c are computed from the values of x1,x2,x3
However, these roots are not nice, so we are left to calculate the values step-by-step:
x4=x3+x1=2+1=3
x5=x4+x2=3+1=4
x6=x5+x3=4+2=6
x7=x6+x4=6+3=9
x8=x7+x5=9+4=13
x9=x8+x6=13+6=19
hence the total number of ways is 19.