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. There are some direct paths between Q and R and between R and S. One can travel from P to S either via Q, via R, or via Q followed by R, in exactly 60 possible ways. One can also travel from Q to R either directly, via P, or via S, in exactly 28 possible ways. Then, the number of direct paths between Q and R is:
Answer and solution
Correct answer: C
Solution
Answer: C — 4
1. Let the number of direct roads between Q and R be x, and the number between R and S be y.
2. First, count the ways to travel from Q to R.
There are x direct ways, 3 × 4 = 12 ways through P, and 4y ways through S.
3. So, x + 12 + 4y = 28
Therefore, x + 4y = 16. ...(1)
4. Now count the ways to travel from P to S.
Through Q: 3 × 4 = 12 ways.
Through R: 4y ways.
Through Q and then R: 3xy ways.
5. So, 12 + 4y + 3xy = 60
Therefore, 4y + 3xy = 48. ...(2)
6. From (1), x = 16 − 4y.
Putting this in (2):
7. 4y + 3y(16 − 4y) = 48
4y + 48y − 12y² = 48
12y² − 52y + 48 = 0
3y² − 13y + 12 = 0
8. This gives y = 3 or y = 4/3. Since the number of roads must be a whole number, y = 3.
9. Using (1), x + 4(3) = 16, so x = 4.
10. Answer: 4.
11. Route check at x=4, y=3: P→S gives 12+12+36=60; Q→R gives 4+12+12=28. The excluded route P→R→Q→S is not among the routes listed in the question.
Why this method works:
A route made of successive legs uses multiplication; alternative listed routes use addition. Thus P→Q→R→S contributes 3xy, not 3+x+y. The restriction to the named routes matters: adding P→R→Q→S would describe a different problem.
Independent check and common trap:
Check the integer restriction before accepting a quadratic root. At y=4/3 the algebra works but a fractional number of roads is impossible. At x=4, y=3 both required route counts match exactly.
Apply: Let QR=x and RS=y. x+4y=16; y(4+3x)=48. Test x=4: y=3 satisfies both. The other algebraic solution has fractional road counts and is excluded.
Check: Check the integer restriction before accepting a quadratic root. At y=4/3 the algebra works but a fractional number of roads is impossible. At x=4, y=3 both required route counts match exactly.
1. Let the number of direct roads between Q and R be x, and the number between R and S be y.
2. First, count the ways to travel from Q to R.
There are x direct ways, 3 × 4 = 12 ways through P, and 4y ways through S.
3. So, x + 12 + 4y = 28
Therefore, x + 4y = 16. ...(1)
4. Now count the ways to travel from P to S.
Through Q: 3 × 4 = 12 ways.
Through R: 4y ways.
Through Q and then R: 3xy ways.
5. So, 12 + 4y + 3xy = 60
Therefore, 4y + 3xy = 48. ...(2)
6. From (1), x = 16 − 4y.
Putting this in (2):
7. 4y + 3y(16 − 4y) = 48
4y + 48y − 12y² = 48
12y² − 52y + 48 = 0
3y² − 13y + 12 = 0
8. This gives y = 3 or y = 4/3. Since the number of roads must be a whole number, y = 3.
9. Using (1), x + 4(3) = 16, so x = 4.
10. Answer: 4.
11. Route check at x=4, y=3: P→S gives 12+12+36=60; Q→R gives 4+12+12=28. The excluded route P→R→Q→S is not among the routes listed in the question.
Why this method works:
A route made of successive legs uses multiplication; alternative listed routes use addition. Thus P→Q→R→S contributes 3xy, not 3+x+y. The restriction to the named routes matters: adding P→R→Q→S would describe a different problem.
Independent check and common trap:
Check the integer restriction before accepting a quadratic root. At y=4/3 the algebra works but a fractional number of roads is impossible. At x=4, y=3 both required route counts match exactly.
G Strategy shortcut
Spot: Combinatorics – Routes and Networks.Apply: Let QR=x and RS=y. x+4y=16; y(4+3x)=48. Test x=4: y=3 satisfies both. The other algebraic solution has fractional road counts and is excluded.
Check: Check the integer restriction before accepting a quadratic root. At y=4/3 the algebra works but a fractional number of roads is impossible. At x=4, y=3 both required route counts match exactly.
G Strategy: Spot: Combinatorics – Routes and Networks. Apply: Let QR=x and RS=y. x+4y=16; y(4+3x)=48. Test x=4: y=3 satisfies both. The other algebraic solution has fractional road counts and is excluded. Check: Check the integer restriction before accepting a quadratic root. At y=4/3 the algebra works but a fractional number of roads is impossible. At x=4, y=3 both required route counts match exactly.