Question

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. $2^9$
• B. $2^{19}$
• C. $\left(\begin{array}{c}8\\ 4\end{array}\right)$ $\times$ $\left(\begin{array}{c}11\\ 5\end{array}\right)$
• D.
  $\left(\begin{array}{c}20\\ 10\end{array}\right)$ - $\left(\begin{array}{c}8\\ 4\end{array}\right)$ $\times$ $\left(\begin{array}{c}11\\ 5\end{array}\right)$

Answer 1

The correct option is D

$\left(\begin{array}{c}20\\ 10\end{array}\right)$ - $\left(\begin{array}{c}8\\ 4\end{array}\right)$ $\times$ $\left(\begin{array}{c}11\\ 5\end{array}\right)$
The robot can reach (4, 4) from (0, 0) in ${}^8$$C_4$ ways as argued in previous problem. Now after reaching (4, 4), robot is not allowed to go to (5, 4). Let us count how many paths are there from (0, 0) to (10, 10) if robot goes from (4, 4) to (5, 4) and then we can subtract this from total number of ways to get the answer.
Now there are ${}^8$$C_4$ ways for robot to reach (4, 4) from (0, 0) and then robot takes the 'U' move from (4, 4) to (5, 4). Now from (5, 4) to (10, 10) the robot has to make 5 'U' moves and 6 'R' moves in any order which can be done in $\frac{11!}{5!6!}$ ways = ${}^{11}$$C_5$ ways.
$\therefore$ The number of ways robot can move from (0, 0), (10, 10) via (4, 4) - (5, 4) move is

${}^8$$C_4$ $\times$ ${}^{11}$$C_5$ = $\left(\begin{array}{c}8\\ 4\end{array}\right)$ $\times$ $\left(\begin{array}{c}11\\ 5\end{array}\right)$
$\therefore$ Number of ways robot can move from (0, 0)
(10, 10) without using (4,4) to (5, 4) move

$\left(\begin{array}{c}20\\ 10\end{array}\right)$ - $\left(\begin{array}{c}8\\ 4\end{array}\right)$ $\times$ $\left(\begin{array}{c}11\\ 5\end{array}\right)$ ways.

which is option (d).