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, 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.
A
- B.
B
- C.
C
- D.
D
Attempted by 40 students.
Show answer & explanation
Correct answer: D
Key idea: count all monotone paths and subtract those that use the forbidden segment.
Total number of monotone paths from (0,0) to (10,10) without any restriction = C(20,10) = 184756.
Number of paths that use the forbidden right move from (4,4) to (5,4):
This equals (number of paths from (0,0) to (4,4)) × (number of paths from (5,4) to (10,10)) = C(8,4) × C(11,5) = 70 × 462 = 32340.
Valid paths that avoid the forbidden segment = total − forbidden = C(20,10) − C(8,4)×C(11,5) = 184756 − 32340 = 152416.
Final answer: 152416