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

We have four towns: P, Q, R, and S. Some towns are connected by direct roads, and others require going through intermediate towns.

Given direct connections:

• P to Q: 3 paths

• Q to S: 4 paths

• P to R: 4 paths

• P to S: 0 paths (no direct connection)

• Q to R: $p$ paths (unknown - this is what we need to find)

• R to S: $q$ paths (unknown)

When traveling between towns with no direct path, we use the multiplication principle: if you can do one thing in $m$ ways and another thing in $n$ ways, then you can do both things in $m \times n$ ways.

For example, if there are 3 ways to go from P to Q and 4 ways to go from Q to S, then there are $3 \times 4 = 12$ ways to go from P to S via Q.

---

From P to S, we can travel in three different ways:

P → Q → S: $3 \times 4 = 12$ ways

P → R → S: $4 \times q$ ways

P → Q → R → S: $3 \times p \times q$ ways

For route 3, we need to choose one path from P to Q (3 choices), then one path from Q to R (p choices), then one path from R to S (q choices).

Total ways from P to S: $12 + 4q + 3pq = 62$

This gives us: $4q + 3pq = 50$

Factoring: $q(4 + 3p) = 50$ ... (Equation 1)

---

From Q to R, we can travel in three different ways:

Q → R directly: $p$ ways

Q → P → R: $3 \times 4 = 12$ ways

Q → S → R: $4 \times q$ ways

Total ways from Q to R: $p + 12 + 4q = 27$

This gives us: $p + 4q = 15$ ... (Equation 2)

---

From Equation 1: $q(4 + 3p) = 50$

Since $p$ and $q$ must be positive integers (representing number of paths), we need to find factor pairs of 50.

Finding factors of 50: $50 = 2 \times 25 = 5 \times 10 = 1 \times 50$

The possible combinations $(q, 4 + 3p)$ are:

$q = 1$, $4 + 3p = 50$ → $3p = 46$ → $p = 15.33...$ (not an integer)

$q = 2$, $4 + 3p = 25$ → $3p = 21$ → $p = 7$ ✓

$q = 5$, $4 + 3p = 10$ → $3p = 6$ → $p = 2$ ✓

$q = 10$, $4 + 3p = 5$ → $3p = 1$ → $p = 0.33...$ (not an integer)

$q = 25$, $4 + 3p = 2$ → $3p = -2$ → $p < 0$ (invalid)

$q = 50$, $4 + 3p = 1$ → $3p = -3$ → $p < 0$ (invalid)

---

Option 1: $p = 7$, $q = 2$

Checking Equation 2: $7 + 4(2) = 7 + 8 = 15$ ✓

Checking Equation 1: $2(4 + 3(7)) = 2(4 + 21) = 2(25) = 50$ ✓

Option 2: $p = 2$, $q = 5$

Checking Equation 2: $2 + 4(5) = 2 + 20 = 22 \neq 15$ ✗

---

Only $p = 7$ and $q = 2$ satisfy both conditions.

Therefore, the number of direct paths between Q and R is 7.