A robot moves from cell (1,1) to the cell (N,N). It has only 2 possible moves: right or down. A kink in the path is called a turn. For example, the path in the figure has 5 turns. The robot can make only 'k' turns.
Find the number of possible paths for:
N=15, K=9.
Example: for N=4 and k=2, the robot needs to go from (1,1) to (4,4) and make only 2 turns. There are 4 possible paths: RRDDDR, RDDDRR, DRRRDD and DDRRRD.
yes its correct.
ReplyDeleteis it 252 ??
ReplyDelete28C9
ReplyDeleteI'd like more people to try this because:
ReplyDelete1)Its not very difficult
2)It will help you revise some PnC (the best revision comes from solving a new problem).
3)I'll be writing a good solution
plz verify answer !!
ReplyDeletehi Abhishek, your answer is wrong.
ReplyDeletethe answer is 1,022,450.
arre itna jyada answer !!!
ReplyDeletewhat i did !!
here i considered 9 pairs of RD & DR arranged in a row such that variables x occupy R and Variables y occupy D ..
(y1)DR(x1)RD(y2)DR(x2)RD(y3)DR(x3)RD(y4)DR(x4)RD(y5)DR(x5)
now we have to divide 5 identical items of one type(viz.R) and 5 of other type(viz.D) in 5 diff groups....
now use the result of integral solution method :-
eqn 1.:: x1+x2+x3+x4+x5=5
eqn 2.:: y1+y2+y3+y4+y5=5
now multiply the result for both the eqn. i.e. 9C5
so answer is 9C5 * 9C5 * 2
2 -- since R & D can change their relative positions ......
where did i go wrong ??
it makes more sense with:
ReplyDeletex1+x2+x3+x4+x5=14
y1+y2+y3+y4+y5=14
There are 14 R's.
ReplyDeleteThere are 15 spaces between these R's including Ends to fill D's.Each space can be filled by ) or more D's.If there are non zero number of D's at the end then it contributes to one turn but non zero number of turns at any other space apart from ends contributes to tw0 turns.Now since there can be 9 turns only so there can only be 5 non zer0 spaces in which one has to be at end.
There are two ends out of which u hv to select 1 which holds non zero D's.There are 13 middle spaces out of which u hv to select 4 which hold's non zero D's.Now there are five variables whose sum has to be 14 and min value =1.Solve the integral eqn and to get solns equal to 13C4.So answr is 2C1 * 13C4 *13C4.
In third line ...i meant to say 0 or more D's.
ReplyDeleteHi Dhwanit. Your solution is correct.
ReplyDeletebut when i have taken DR & RD pairs why do i need to take them in my equation???? these arranged pairs need not be arranged again ?? .....??
ReplyDeleteHi Abhishek. I see that your answer is not affected by the choice of N. I do not understand your solution but something is definitely wrong.
ReplyDeleteyaa it is affectd !!
ReplyDeleteif i take N=16 and turns to be 9 then RHS of my equation becomes 6 .(not 5 )
treat R,D as identical items.
arrange them in a row such that R->D & D-> R change occur 9 times ....
hope u will now catch the incorrect part of my answer !!
lpz help me out !!!
ReplyDeleteDoes your solution take care of the ***RDR** case?
ReplyDeleteYou're using links, which only allows solutions of the form ****RD***DR***