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

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

Accepted Answer

7 — Hard Let $Q\!-\!R$ have $x$ paths and $R\!-\!S$ have $y$ paths. Count routes by the multiplication principle for each described option, form two equations, and solve the resulting quadratic for $x$. 1 P to S in 62 ways. Paths: $PQ=3,\ QS=4,\ PR=4$. Routes: via Q $(P\,Q\,S)=3\cdot4$; via R $(P\,R\,S)=4y$; via Q then R $(P\,Q\,R\,S)=3xy$. $$\begin{aligned} &12+4y+3xy=62\ &\Rightarrow\ 4y+3xy=50 \end{aligned}$$ 2 Q to R in 27 ways. Routes: directly $=x$; via P $(Q\,P\,R)=3\cdot4$; via S $(Q\,S\,R)

CAT 2024 Slot 2 — QA Question 19

Answer & solution