The number of shortest paths from point A to | vedclass

Name: Exam Paper Generator | JEE NEET Paper Generator | Vedclass
Brand: Vedclass
Rating: 5 (35 reviews)

Question

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths f

Vedclass · Accepted Answer

$186$

Vedclass · Answer

(B) To find the number of shortest paths from $A$ to $D$,we observe that all paths must pass through the segment $MN$. Let $S_M$ be the set of paths from $A$ to $M$ and $S_N$ be the set of paths from $A$ to $N$. Paths from $A$ to $M$: The grid from $A$ to $M$ is $2$ units wide and $5$ units high. The number of paths is $\frac{(2+5)!}{2!5!} = \frac{7!}{2!5!} = 21$. Paths from $M$ to $D$: The grid from $M$ to $D$ is $2$ units wide and $2$ units high. The number of paths is $\frac{(2+2)!}{2!2!} = \frac{4!}{2!2!} = 6$. Total paths through $M$ = $21 	imes 6 = 126$. Paths from $A$ to $N$: The grid from $A$ to $N$ is $2$ units wide and $4$ units high. The number of paths is $\frac{(2+4)!}{2!4!} = \frac{6!}{2!4!} = 15$. Paths from $N$ to $D$: The grid from $N$ to $D$ is $2$ units wide and $3$ units high. The number of paths is $\frac{(2+3)!}{2!3!} = \frac{5!}{2!3!} = 10$. Total paths through $N$ = $15 	imes 10 = 150$. Since the segment $MN$ is a single vertical step,any path passing through $M$ must pass through $N$ (or vice versa depending on direction). However,the grid structure shows $M$ is above $N$. Thus,any path from $A$ to $D$ must pass through the segment $MN$. The number of paths through $MN$ is the number of paths from $A$ to $N$ multiplied by the number of paths from $M$ to $D$. Paths through $MN = (	ext{Paths } A 	o N) 	imes (	ext{Paths } M 	o D) = 15 	imes 6 = 90$. Using the Principle of Inclusion-Exclusion for paths through $M$ or $N$: Total paths = (Paths through $M$) + (Paths through $N$) - (Paths through both $M$ and $N$) Total paths = $126 + 150 - 90 = 186$.

The number of shortest paths from point $A$ to $D$ (as shown in the figure) is:

Similar Questions

In how many different ways can the letters of the word '$DETAIL$' be arranged in such a way that the vowels occupy only the odd positions?

There are $10$ lamps in a hall. Each one of them can be switched on independently. The number of ways in which the hall can be illuminated is

Four dice (six-faced) are rolled. The number of possible outcomes in which at least one die shows $2$ is

The number of words that do not start and end with vowels,formed using all the letters of the word $UNIVERSITY$ such that all vowels are in alphabetical order,is

The number of $7$-digit numbers which can be formed using the digits $1, 2, 3, 2, 3, 3, 4$ is:

Vedclass Test Series

Exam Paper Generator

Online Exam Module