CAT 2024 Slot 2 QA Question 18

Type-in-the-answer (no negative marking) · Modern Math · Permutation & Combination · Try it, then check the answer and solution below.

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
TITA Answer:
Answer and solution

Answer: 7

📌 Core Concept
This problem involves graph theory, specifically counting the number of paths between nodes. We use the multiplication principle for counting paths through intermediate nodes.
🔢 Step-by-Step Solution
1
Define Variables:
Let xx be the number of direct paths between Q and R.
Let yy be the number of direct paths between R and S.
2
Set Up Equations:
From P to S:
Via Q: 3×4=123 \times 4 = 12 ways.
Via R: 4×y4 \times y ways.
Via Q then R: 3×x×y3 \times x \times y ways.
Total: 12+4y+3xy=6212 + 4y + 3xy = 62.
Simpl

Keep going

Related Permutation & Combination questions