CAT 2024 Slot 2 · Quant · Question 11

Let the unknown counts be x direct paths between Q and R, and y direct paths between R and S.

The known counts are 3 between P and Q, 4 between Q and S, and 4 between P and R.

Routes from P to S via Q only use P–Q then Q–S, giving 3\times 4=12 ways.

Routes via R only use P–R then R–S, giving 4\times y=4y ways.

Routes via Q followed by R use P–Q, then Q–R, then R–S, giving 3\times x\times y=3xy ways.

Their total is 62, so 12+4y+3xy=62, that is 4y+3xy=50.

Routes from Q to R directly number x; via P they are Q–P then P–R, giving 3\times 4=12; via S they are Q–S then S–R, giving 4\times y=4y.

Their total is 27, so x+12+4y=27, that is x+4y=15.

Substituting 4y=15-x into 4y+3xy=50 gives 15-x+3xy=50, so 3xy=35+x.

Also y=\frac{15-x}{4}, and putting that in, \frac{3x\left( 15-x \right)}{4}=35+x.

Clearing the denominator, 45x-3{x}^{2}=140+4x, which rearranges to 3{x}^{2}-41x+140=0.

The discriminant is {41}^{2}-4\times 3\times 140=1681-1680=1, so x=\frac{41\pm 1}{6}.

That gives x=7 or x=\frac{40}{6}, and only x=7 is a whole number of paths.

Checking, y=\frac{15-7}{4}=2, and then 12+8+42=62 and 7+12+8=27 both hold.

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

Shortcut. The second condition, x+4y=15, has very few whole-number solutions: the pairs \left( x,y \right) can only be \left( 11,1 \right), \left( 7,2 \right) or \left( 3,3 \right). Testing these three against 4y+3xy=50 finds \left( 7,2 \right) at once, with no quadratic needed.