39i am scared to edit it as all words will come together once i press edit...!!!!!!
nishant bhaiyan u please do it..
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
39
1um ok!
let me try ...
if xn is the no. of ways to tile n x 3 floor with 3 x 1 tiles ....
(over here n = 3k as i assume )
case 1 :
1st tile is horizontal.. that means we have covered 3 units in breadth (doesn't it) also we have no other option for the space 3 x 2 space beneath..
so no. of ways when the first tile is horizontal = xn-3 (ISN'T IT?)
now case 2 :
1st tile is vertical... This invariably means that we got to cover 2 x 3 space more with vertical tiles.. now these tiles can be placed in a no. of ways (provided the distance b/w them is either 0 or 3)....(say k)
so no. of ways now to lay the tiles = k(xn-3)
[7]
62No we have not asumed that n=3k
if n=1
then no of way is one...
place the tile vertically...
1ok that starts to make some sense....
then the only problem is that b55 should swap the words horizontal and vertical !
and he agreed that n = 3k when i asked him :P
1but if n ≠3k then how can we justify this statement :
"If the first tile (occupying the top-left corner) is vertical, we cannot avoid using two more vertical tiles adjacently to it"
62I guess b555 has made a small mistake in the explanation
basically if we use one vertical tile.. then we still have to fill n-1x3 floor.. the number of ways of which is Tn-1
Now if we fill one tile horzontally... then twox3 space will be left above it.. so they also have to be filled horizontally.. hence we will be left with a (n-3)x3 floor...
So Tn=Tn-1+Tn-3
From there.. just calculate T1, T2 and T3 manually.. as 1, 1, and 2 (is that obvious?)
Then use reccursion to find the other values
1this is better ...
its simple if we have to calculate manually after all
I was trying to discuss this with b555 and we both made hell of the communication :D
edit : removed a biased (and ignorant) thought
62Yes it still has a beautiful solution (Atleast to me.. even though this idea is often overused)
because the recurrence relation can be solved.. but that is a different thing altogether.. and mostly not in syllabus... (Albeit not very difficult)
moreover, you will see the beauty when you realze that with this idea, you can easily find the number of ways to file a
mxn floor using 1xm tiles.. for any value of m and n
39hey philip sorry for acepting that n=3k. i must have been mad to do that...
ya i did small mistake.. i wrongly typed verticlal and horozontal....
but thats enough for a half understood guy to go mad
62Then use firefox :P
I dont like Chrome (and yeah the site has issues with chrome)
1stilll i am not able able to get why are u adding both ,and sir barghav has not explained why we are adding
62Let me try to
there are only 2 ways to fill the left most slot
either the tile is placed vertically, in which case, there are n-1 tiles to be filled...
or the tile can be placed horizontally. If the tile is placed horizontally, the three slots should all have horizontal tiles..
which means that we have to still fill n-3 slots
and the two methods above are exclusive and exhaustive..
hence
Tn=Tn-1+Tn-3
62http://targetiit.com/iit-jee-forum/posts/07-10-09-toss-a-coin-n-times-so-that-there-are-no-11745.html also the answer matches because the events you have taken are exclusive and exhaustive
think properly :)
1Then the ways are 19...
(Or I have messed up yet again[7])
62I was more worried about the number of views of this post.. :) (now that seems to be picking up :D)
It is a teaching question which i use for explaining recursion in the class [1]
1I just worked it up in my mind...used symmetry arguments...
(Have I messed it up completely??)
39listen guys:
you distinguish two cases:
1) the leftmost tiles are horizontal
2) the leftmost tile is vertical
and thus you get, by induction, a recurrencce