Skip to content
GATETECH
Official PYQ · 2007Q85Combinatorics: Counting, Recurrence Relations, Generating FunctionsMCQ1 mark

GATE CS 2007 Q85 — Combinatorics: Counting, Recurrence Relations, Generating Functions

Explain with AI

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)(i,j) then it can move to either (i+1,j)(i + 1, j) or (i,j+1)(i,j + 1).

Suppose that the robot is not allowed to traverse the line segment from (4,4)(4,4) to (5,4)(5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10)(10,10) starting from (0,0)(0,0)?

Choose one option
View worked solution

Answer: D

To find the number of distinct paths from (0,0)(0,0) to (10,10)(10,10) that do not traverse the line segment from (4,4)(4,4) to (5,4)(5,4), we can use the principle of subtraction:

Allowed Paths=Total Paths−Paths traversing the forbidden segment\text{Allowed Paths} = \text{Total Paths} - \text{Paths traversing the forbidden segment}

Step 1: Total paths from (0,0)(0,0) to (10,10)(10,10)

To reach (10,10)(10,10) from (0,0)(0,0), the robot must take exactly 1010 Right (R) steps and 1010 Up (U) steps, making a total of 2020 steps.

The number of ways to arrange these steps is:

Ntotal=(2010)=20C10N_{\text{total}} = \binom{20}{10} = {}^{20}\mathrm{C}_{10}

Step 2: Paths traversing the forbidden segment from (4,4)(4,4) to (5,4)(5,4)

Any path that traverses this specific segment must be broken down into three consecutive parts:

  1. Path from (0,0)(0,0) to (4,4)(4,4): Requires 44 Right steps and 44 Up steps (total 88 steps). N1=(84)=8C4N_1 = \binom{8}{4} = {}^{8}\mathrm{C}_{4}
  2. Step from (4,4)(4,4) to (5,4)(5,4): This is exactly 11 fixed Right step. N2=1N_2 = 1
  3. Path from (5,4)(5,4) to (10,10)(10,10): Requires 10−5=510 - 5 = 5 Right steps and 10−4=610 - 4 = 6 Up steps (total 1111 steps). N3=(115)=11C5N_3 = \binom{11}{5} = {}^{11}\mathrm{C}_{5}

By the product rule, the number of paths traversing the forbidden segment is:

Nforbidden=8C4×1×11C5=8C4×11C5N_{\text{forbidden}} = {}^{8}\mathrm{C}_{4} \times 1 \times {}^{11}\mathrm{C}_{5} = {}^{8}\mathrm{C}_{4} \times {}^{11}\mathrm{C}_{5}

Step 3: Allowed paths

Subtracting the forbidden paths from the total paths gives:

Allowed Paths=20C10−8C4×11C5\text{Allowed Paths} = {}^{20}\mathrm{C}_{10} - {}^{8}\mathrm{C}_{4} \times {}^{11}\mathrm{C}_{5}

Thus, the correct option is D.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Combinatorics: Counting, Recurrence Relations, Generating Functions questions