Question

P, Q, R and S are four towns. One can travel between P and Q along 3 direct paths, between Q and S along 4 direct paths, and between P and R along 4 direct paths. There is no direct path between P and S, while there are few direct paths between Q and R, and between R and S. One can travel from P to S either via Q, or via R, or via Q followed by R, respectively, in exactly 62 possible ways. One can also travel from Q to R either directly, or via P, or via S, in exactly 27 possible ways. Then, the number of direct paths between Q and R is

Answer 1

Correct Answer: 7

Let the number of direct paths between Q and R be $x$, and between R and S be $y$. 

Given:
- Paths between P and Q = $3$
- Paths between Q and S = $4$ 
- Paths between P and R = $4$
- No direct path between P and S. 

Total paths from P to S = 62
Paths from P to S:

• Via Q: $3 \times 4 = 12$
• Via R: $4 \times y = 4y$
• Via Q then R: $3 \times x \times y = 3xy$

So, $12 + 4y + 3xy = 62$ $\Rightarrow 3xy + 4y = 50 \quad \text{(1)}$ 

Total paths from Q to R = 27
Paths from Q to R:

• Direct: $x$
• Via P: $3 \times 4 = 12$
• Via S: $4 \times y = 4y$

So, $x + 12 + 4y = 27$ $\Rightarrow x + 4y = 15 \quad \text{(2)}$ 

From (2): $x = 15 - 4y$ Substitute into (1): $3(15 - 4y)y + 4y = 50$ $\Rightarrow 45y - 12y^2 + 4y = 50$ $\Rightarrow -12y^2 + 49y = 50$ $\Rightarrow 12y^2 - 49y + 50 = 0$ 

Solving the quadratic:
$y = \frac{49 \pm \sqrt{(-49)^2 - 4 \cdot 12 \cdot 50}}{2 \cdot 12}$ $= \frac{49 \pm \sqrt{2401 - 2400}}{24}$ $= \frac{49 \pm 1}{24}$ $\Rightarrow y = 2$ (valid) or $y = \frac{50}{24}$ (not valid) 

So, $y = 2$ Then from (2): $x = 15 - 4 \times 2 = 7$ 

∴ Number of direct paths between Q and R is $7$.