Suppose that a robot is placed on the Cartesian plane. At each step, it is…
2007
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. That is, if the robot is at position (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.
C(20, 10)
- B.
2^20
- C.
2^10
- D.
None of the above
Attempted by 73 students.
Show answer & explanation
Correct answer: A
Given:
A robot starts at (0,0) and wants to reach (10,10). At each step, it can move either:
- One unit Right: (i,j) → (i+1,j)
- One unit Up: (i,j) → (i,j+1)
Solution:
To reach x = 10 from x = 0, the robot must make exactly 10 Right (R) moves.
To reach y = 10 from y = 0, the robot must make exactly 10 Up (U) moves.
Therefore, every valid path consists of:
10 Right moves + 10 Up moves = 20 total moves
Each path can be represented as a sequence of 20 moves containing exactly:
- 10 R's
- 10 U's
(for example: RRRRRRRRRRUUUUUUUUUU or RURURURURURURURURURU).
The problem reduces to finding the number of ways to choose the positions of the 10 Right moves among the 20 total positions.
Number of distinct paths = C(20,10)
= 20! / (10! × 10!)
Hence, the number of distinct paths is:
C(20,10)
Correct Option: (A)