GATE CSE 2007 | Question: 84

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

How many distinct paths are there for the robot to reach the point $(10,10)$ starting from the initial position $(0,0)$?

• A. $^{20}\mathrm{C}_{10}$
• B. $2^{20}$
• C. $2^{10}$
• D. None of the above

Comments

Useful resource to solve these problems: https://betterexplained.com/articles/navigate-a-grid-using-combinations-and-permutations/

---

why option (b) 2^20 cannot be the answer?
longest distance 20 units a robot has to travel, with 2 choices at every step, i.e. up or right, so i believe 2^20 could be a possible answer. Please comment/explain.

---

https://www.youtube.com/watch?v=riyqOPgRC64&list=PLC36xJgs4dxHRZ1t4k5kaktezmYWkrOP7&index=19

Answer 1

problems like these should be solved using movements ( UP , RIGHT )

see this 

Answer 2

The answer for 84 is A. It is same as selecting 10 out of 20 elements.

Comments

₂₀C₁₀ or 2¹⁰?

---

It is 20 C 10.

Answer 3

To reach from $(0,0)$ to $(10,10)$ we have to take 20 steps.

Lets assume these 20 steps to be 20 places.

( _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ )

Out of these 20 places to have to choose 10 places for upper steps, the rest of the 10 places have to be for right steps.)

like one example is  ( _ u u _ _ u _ _ u _ _uuu_ _u_u_ _ _ _ u), the $‘– ‘$ places should be for right steps.

so, Option $A$  $2nCn$​ is the answer.

Comments

Good explanation. Mentioning that : 

Out of these 20 places to have to choose 10 places for upper steps, the rest of the 10 places have to be for right steps.)
 

Here $20 = 2*10$ i.e, $(2n)$ and choosing $10 $ i.e, $(n)$ and $10$ i.e, $(n) = (2n!)/(n!)(n!) = 2nCn$

---

Exactly @Abhrajyoti00

Answer 4

In order to move from (0,0) to (10,10)there will be total 20 movement out of which there will be 10 right,10 upward movement combination

so 20!/10!.10!= c(20,10)