26 votes

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)$?

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

62 votes

Best answer

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}$

0

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

How can we so definit about this ? Didn't get that point

- 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!

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....

6 votes

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.

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 ^{8}C_{4} and ^{11}C_{5} has come? ^{20}C_{10} 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.

5 votes

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.

4 votes

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)**