edited by
9,348 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}$
edited by

5 Answers

Best answer
85 votes
85 votes

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

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.

Answer:

Related questions

34 votes
34 votes
4 answers
1
Kathleen asked Sep 21, 2014
10,004 views
What is the maximum number of different Boolean functions involving $n$ Boolean variables?$n^2$$2^n$$2^{2^n}$$2^{n^2}$
64 votes
64 votes
15 answers
3
Arjun asked Jul 6, 2016
36,697 views
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 \...
30 votes
30 votes
2 answers
4
go_editor asked Apr 23, 2016
9,840 views
Consider the following program segment. Here $\text{R1, R2}$ and $\text{R3}$ are the general purpose registers.$$\begin{array}{|l|l|l|c|} \hline & \text {Instruction} & \...