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 $x$ be the number of direct paths from Q to R, and $y$ be the number of direct paths from R to S.

Given:
- Paths from P to Q = 3
- Paths from Q to S = 4
- Paths from P to R = 4
- No direct path from P to S.

Total paths from P to S = 62
Paths from P to S can be calculated as follows:

• Through Q: Paths P to Q × Paths Q to S = $3 \times 4 = 12$
• Through R: Paths P to R × Paths R to S = $4 \times y = 4y$
• Through Q then R: Paths P to Q × Paths Q to R × Paths R to S = $3 \times x \times y = 3xy$

Therefore, the total paths from P to S is the sum of these: $12 + 4y + 3xy = 62$.
This simplifies to: $3xy + 4y = 50 \quad \text{(1)}$

Total paths from Q to R = 27
Paths from Q to R can be calculated as follows:

• Direct paths: $x$
• Through P: Paths Q to P × Paths P to R = $3 \times 4 = 12$
• Through S: Paths Q to S × Paths S to R = $4 \times y = 4y$

Therefore, the total paths from Q to R is the sum of these: $x + 12 + 4y = 27$.
This simplifies to: $x + 4y = 15 \quad \text{(2)}$

From equation (2), we can express $x$ in terms of $y$: $x = 15 - 4y$.
Substitute this expression for $x$ into equation (1): $3(15 - 4y)y + 4y = 50$.
Expanding this equation: $45y - 12y^2 + 4y = 50$.
Rearranging the terms: $-12y^2 + 49y = 50$.
Further rearrangement to form a standard quadratic equation: $12y^2 - 49y + 50 = 0$.

Solving the quadratic equation for $y$ using the quadratic formula:
$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 \sqrt{1}}{24}$ $= \frac{49 \pm 1}{24}$.
This gives two possible solutions for $y$: $y = \frac{49 + 1}{24} = \frac{50}{24}$ (which simplifies to $\frac{25}{12}$) or $y = \frac{49 - 1}{24} = \frac{48}{24} = 2$.
Since the number of paths must be a whole number, $y = \frac{25}{12}$ is not valid.
Therefore, $y = 2$.

Now, substitute the value of $y$ back into equation (2) to find $x$: $x = 15 - 4 \times 2 = 15 - 8 = 7$.

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