Paths Between Four Towns

CAT 2024 Slot 2 · QA · Medium · Combinatorics

All CAT 2024 Slot 2 questionsMore Combinatorics questionsAll CAT QA

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

Answer

7

Explanation

Let xx be the number of direct paths between Q and R, and yy be the number of direct paths between R and S.

Given paths:

  • N(P,Q)=3N(P, Q) = 3
  • N(Q,S)=4N(Q, S) = 4
  • N(P,R)=4N(P, R) = 4
  • N(P,S)=0N(P, S) = 0

Paths from P to S:

  1. P→Q→S=3×4=12P \to Q \to S = 3 \times 4 = 12
  2. P→R→S=4×y=4yP \to R \to S = 4 \times y = 4y
  3. P→Q→R→S=3×x×y=3xyP \to Q \to R \to S = 3 \times x \times y = 3xy Total ways =12+4y+3xy=62  ⟹  4y+3xy=50  ⟹  y(4+3x)=50= 12 + 4y + 3xy = 62 \implies 4y + 3xy = 50 \implies y(4 + 3x) = 50.

Paths from Q to R:

  1. Direct =x= x
  2. Q→P→R=3×4=12Q \to P \to R = 3 \times 4 = 12
  3. Q→S→R=4×y=4yQ \to S \to R = 4 \times y = 4y Total ways =x+12+4y=27  ⟹  4y=15−x= x + 12 + 4y = 27 \implies 4y = 15 - x.

Substitute 4y=15−x4y = 15 - x into 4×y(4+3x)=2004 \times y(4 + 3x) = 200: (15−x)(4+3x)=200(15 - x)(4 + 3x) = 200 60+41x−3x2=200  ⟹  3x2−41x+140=060 + 41x - 3x^2 = 200 \implies 3x^2 - 41x + 140 = 0 (3x−20)(x−7)=0(3x - 20)(x - 7) = 0

Since xx must be an integer, x=7x = 7.

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace