Multiple choice

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

  2. 219
  3. $ ^{8}C_{4} \times^{11}C_{5}$
  4. $ ^{20}C_{10} - ^{8}C_{4}\times ^{11}C_{5}$
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

Total paths from (0,0) to (10,10) without restriction: 20C10 (choose 10 right moves out of 20). The forbidden edge (4,4)→(5,4) blocks paths going through it. Paths through this edge = paths to (4,4) × paths from (5,4) to (10,10) = 8C4 × 11C5. Subtract to get valid paths.

Keep practicing — related questions