# GATE2007-85

3k views

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$.

Suppose that the robot is not allowed to traverse the line segment from $(4,4)$ to $(5,4)$. With this constraint, how many distinct paths are there for the robot to reach $(10,10)$ starting from $(0,0)$?

1. $2^9$
2. $2^{19}$
3. $^{8}\mathrm{C}_{4} \times^{11}\mathrm{C}_{5}$
4. $^{20}\mathrm{C}_{10} - ^{8}\mathrm{C}_{4}\times ^{11}\mathrm{C}_{5}$

edited
2
(All possible moves from (0,0) to (10, 10)) - (All possible moves from (0,0) to (10, 10) in which (4,4) to (5,5) is always traversed)
5

Say, $r = \text{Move Right}$ and $u = \text{Move Up}$
so using ${10}$ combination of $r$ and ${10}$ combinations of $u$ moves we get a solution.

Convert the graphical moves to text and one such solution we get,

$=\{u, u, u, u, u, u, u, u, u, u, r, r, r, r, r, r, r, r, r, r\}$

now all possible arrangements of them is given by = $\frac{20!}{10! \times 10!} = {20 \choose 10}$

now we need to discard the segment move from $(4,4)$ to $(5,4)$:

to do that we first calculate how many solutions to our problem to reach $(10, 10)$ involves that segment.

We'll then subtract those solutions from the total number of solutions.
Number of solutions to reach from$\left(0,0\right)$ to $\left(4,4\right),$

$=$all possible arrangements of $\{r, r, r, r, u, u, u, u\}$

$=\frac{(4+4)!}{4! \times 4!} = {8 \choose 4}$

definitely we take the segment $\left(4,4\right) \text{to} \left(5,4\right) = 1.$

now, Number of solutions to reach from $\left(5,4\right) \text{to} \left(10,10\right),$

$=$ all possible arrangements of $\{r, r, r, r, r, u, u, u, u, u, u\}$

$=\frac{(6+5)!}{6! \times 5!} = {11 \choose 5}$

so required number of solutions for Q.85 is given by option D
i.e. $={20 \choose 10} - {8 \choose 4} \times 1 \times {11 \choose 5}$

edited
0

definitely we take the segment (4,4) to (5,4) = 1

• after reaching (4,4) cant we go (4,5) ?
7
when he is describing the path from (4,4 to 5,4), the definately point which you are making is because we want to count all those path which goes from that perticular line segment. at that point he is counting all the different possible path which can be formed by taking this line segment. the one whcih you are taking that can't we go to 4,4 to 4,5 is valid path which is counted when we are taking 20c10. so now as we want to subtract all those path which are part of this only segment. read the ques. again and my point and i guess you will get it. let me know if in case u don't!
0
Marvelous explanation thanks! :)
0

Well explained.Thanks:)

1
No u can't go bcz ways to (4,4) have been blocked so no chances to go (5,4) from (4,4) but still there are chances of (5,4) occurance like if we are on (4,3) then one right and one up will give (5,4) which is not come from (4,4) so that further ways have been blocked starting from (5,4) by this way (5,4) occurance have been vanished....
0
all possible arrangements of {r,r,r,r,r,r,u,u,u,u,u}{r,r,r,r,r,r,u,u,u,u,u}

=(6+5) / !6!×5!=(11 C 5 )

why 11 C 5...whynot 11C 6
0
great explanation @amarvashistha
0

Its equal : C(11,5) = C(11,6)

as C(n,r)=C(n,n-r)

0
Awesome explanation.
Let us think this way.

If we can find all the paths through (4,4) and (5,4), then subtracting the result from all the possibilities should give us the answer.

So, moving to finding the paths passing through (4,4) and (5,4)

Starting from (0,0), we need 4 ups and 4 rights to go to (4,4). So we have 8C4 ways of doing that.

Similarly from (5,4) to (10,10) we need 6 ups and 5 rights. So we have 11C6 ways of doing that.

Total number of paths from (0,0) to (10,10) are 20C10.

So our answer will be 20C10 - (8C4)*(11C6) which is option d.
4

@Satyandra, For simplicity sake I m sharing a diagrammatic representation of d ques. So as far as I've understood d path b/w (0,0) and (4,4) I've highlighted in d fig.Similarly d path between (5,4) and (10,10) as well. But please tell how 8C4 and 11C5 has come? 20C10 is still okay.

It'll be a big help indeed.

0
now see in the total paths counted i.e 20C10 u must have counted those paths too which have (4,4) as a point  in between .Now if u want to find paths then just find the number of paths that lead to (4,4) and then go on to (5,4) and then to (10,10).This gives us the number of paths that can't be traversed and we can finally subtract this number from the total paths possible i.e.20C10.so if u are at (5,4) u need to have 5 down moves and 6 right moves giving us 11 moves in total .(11!/5!*6!)*(8!/4!*4!)(for (0,0)to (4,4)).this can be subtracted from 20C10.
0

check this one

At each move, robot can move either 1 unit right, or 1 unit up, and there will be 20 such moves required to reach (10,10) from (0,0). So we have to divide these 20 moves, numbered from 1 to 20, into 2 groups : right group and up group. Right group contains those moves in which we move right, and up group contains those moves in which we move up. Each group contains 10 elements each. So basically, we have to divide 20 things into 2 groups of 10 10 things each, which can be done in 20!/(10! ☓10!)=20C10 ways.

Since we are not allowed to traverse from (4,4) to (5,4). So we will subtract all those paths which were passing through (4,4) to (5,4).
To count number of paths passing through (4,4) to (5,4), we find number of paths from (0,0) to (4,4), and then from (5,4) to (10,10).
From (0,0) to (4,4), number of paths = 8C4 (found in same way as in previous question).
From (5,4) to (10,10), number of paths = 11C5. (from (4,4) to (5,4) is just one move)
So total number of paths required : 20C10−8C4☓11C5.
So option (D) is correct.

The above grid represents the question with red portion marked as part of path which must not be used by the robot to travel to (10,10) from (0,0).

A robot can only make either right move or up move.

Total up moves possible to reach (10,10) from (0,0)=10

Total right moves needed to reach (10,10) from (0,0)=10

Total moves that need to be taken to reach (10,10) from (0,0)=20.

So, total number of ways to reach (10,10) from (0,0) without any constraint = 20C10*10C10=20C10

i.e. first select right moves first from available 20 moves and then select up moves from rem 10 moves.

Now, the robot in order to reach (10,10) cannot use path from (4,4) to (5,4)

So our answer will be given by

Total paths - No. of paths in which path (4,4)->(5,4) is involved.

Now we need to calculate No. of paths in which path (4,4)->(5,4) is involved.

which will be given by

Number of ways to reach (4,4) from (0,0) (Say p1) X Number of ways to reach (4,4)->(5,4) (say p2) X Number of ways to reach (10,10) from (5,4) (say p3)

p1- Total 8 moves from (0,0) to (4,4) and then first we select right move and then up move. 8C4 ways.

p2-Only 1 way.

p3-Total 11 moves from (5,4) to (10,10) in which we select first 5 right moves and then remaining 6 up moves- 11C5 ways.

hence p1 X p2 X p3 = 8C4 * 11C5

Hence, answer would be 20C10 - (8C4 *11C5) (d)

0
Sir Shouldn't (5,4) be above (4,4) ?
0

## Related questions

1
2.9k views
What is the maximum number of different Boolean functions involving $n$ Boolean variables? $n^2$ $2^n$ $2^{2^n}$ $2^{n^2}$
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at $(i,j)$ then it can move to either $(i + 1, j)$ or $(i,j + 1)$. How many distinct paths are there for the robot to reach the point $(10,10)$ starting from the initial position $(0,0)$? $^{20}\mathrm{C}_{10}$ $2^{20}$ $2^{10}$ None of the above
Consider the following segment of C-code: int j, n; j = 1; while (j <= n) j = j * 2; The number of comparisons made in the execution of the loop for any $n > 0$ is: $\lceil \log_2n \rceil +1$ $n$ $\lceil \log_2n \rceil$ $\lfloor \log_2n \rfloor +1$
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ ... interrupt occurs during the execution of the instruction INC R3 , what return address will be pushed on to the stack? $1005$ $1020$ $1024$ $1040$