CAT 2008 | Question: 03

Question

Direction for the question given below

The figure below shows the plan of a town. The streets are at right angles to each other. A rectangular park $\text{(P)}$ is situated inside the town with a diagonal road running through it. There is also a prohibited region $\text{(D)}$ in the town

Neelam resides her bicycle from her house at $\text{A}$ to her office at $\text{B}$, taking the shortest path, then the number of possible shortest paths that she can choose is

• A. $60$
• B. $75$
• C. $45$
• D. $90$
• E. $72$

Answer 1

90

We can find the number of shortest possible paths from A to E either by trial and error or by using combinations. Note that to travel from A to E, we have to take 2 roads to the right and 2 roads downwards (in the diagram) in order that we follow the shortest path. In other words, we have to use 2 + 2 = 4 roads, out of which 2 are towards right and 2 are downwards. This is equivalent to selecting 2 things (roads towards right) out of 4 things (roads). (The remaining two roads will be downwards.) The number of ways of doing this is 4C2 = 4!/(2!×2!) = 6 From point A to E, there are 6 ways to reach with the minimum distance travelled. Here E to F is the shortest distance because the third side of a triangle is always less than the sum of the other two sides.

From point F to B, there are 6C4 = 6!/(4!×2!) = 15 ways to reach with the minimum distance travelled. There are 15 × 6 = 90 shortest paths that Neelam can choose

Comments

The point why she should reach E is not clear..

---

So that she can get diagonal path

---

Yes, thats the most beautiful part of the answer - should be clear :)

---

To avoid 4 roads(Two to right and Two to left), so as to make it minimum, we are bound to go through diagonal and so every path will contain EF in their route.

Answer 2

The answer provided in the previous post is right but the explanation is incorrect.

The shortest path will be A → E → F→ B. Because the entire map is symmetric but the diagonal creates a new shorter path from E→ F. Diagonal is shorter than the sum of its perpendicular and base (Pythagoras Theorem’s Corollary).

Now to go from A to E, we have to travel right two times and travel downwards two times. So, we could for example, take R, D, R and D or we could take R, R, D, D. So how many such arrangements are possible ?? Lets list them down :-

R R D D, D D R R, R D R D, D R D R, R D D R, D R R D – Six arrangements possible

So the questions is how many permutations/arrangements of these four roads (R R D D) is possible given two of them are repeating twice.

It is : $\large \frac{^{4} P_{4}}{2!*2!} = \frac{4!}{2! * 2!} = 6$

Similarly, for F to B, we have to take four rights and two downs (R R R R D D). So the number of arrangements of these six roads, one which repeats twice and the other repeats four times is :

 $\large \frac{^{6} P_{6}}{4!*2!} = \frac{6!}{4! * 2!} = 15$

Therefore, the total number of ways are :  $\large 6 *15 = 90$.

Comments

Nice Explanation!