GATE CSE 2007 | Question: 85

Question

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

• A. $2^9$
• B. $2^{19}$
• C. $^{8}\mathrm{C}_{4} \times^{11}\mathrm{C}_{5}$
• D. $^{20}\mathrm{C}_{10} - ^{8}\mathrm{C}_{4}\times ^{11}\mathrm{C}_{5}$

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)

---

https://www.youtube.com/watch?time_continue=24&v=SbEtwrJH5zc

Answer 1

realize that,

to go from $(a,b) \rightarrow (n,m)$ using the given 2 moves only – “one unit up” or “one unit right”

it will always take exact total of $(n-a) + (m–b)$ moves out of which $(n-a)$ have to be one unit up and $(m-b)$ have to be one unit down

so this tells us

number of ways to go from(a,b) to (n,m) = select (n-a) moves which will be up out of the total (n-a + m-b) moves

i.e $n-a+m-b \choose n-a$

$$\text{ans} = [ (0,0)\rightarrow(10,10) ] \ – \  [[(0,0)\rightarrow(4,4)] \ \times \  [(4,4)\rightarrow(5,4)] \ \times \ [(5,4)\rightarrow(10,10)] ]$$

$$ans = \binom{10+10}{10}  – \binom{4+4}{4}\times1\times\binom{10-5+10-4}{10-5}$$