in Combinatory edited by
9,331 views
36 votes
36 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)$?

  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}$
in Combinatory edited by
9.3k views

2 Comments

(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
5

5 Answers

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

edited by

4 Comments

Nice answer.

Btw to go from (5,4) to (10,10), shouldn’t it be 5 u’s and 6r’s?
0
0
amazing explanation
0
0

@amarVashishth From (5,4) to (10,10) have to take 5u’s and 6r’s. Even though it will be the same cause as 11C5 or 11C6.

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

3 Comments

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

4
4
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
0

check this one

1
1
6 votes
6 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)

3 Comments

Sir Shouldn't (5,4) be above (4,4) ?
0
0
0
0
Much underrated ans:(
0
0
5 votes
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.

by
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true