CAT 2024 Slot 2 Quant Q18

  • Quantitative Aptitude
  • Modern Math › Permutation & Combination
  • Hard
  • Type in the answer (TITA)
  • CAT_2024_SLOT2_QA_Q18

Question 18

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

Type-in-the-answer (TITA) question: no options are given; enter the value.

Answer this question Opens in practice mode, free, no sign-in.

Show answer and solution

Answer:

7

Solution

  • Translate to equations: Let Q↔R=xQ \leftrightarrow R = x and R↔S=yR \leftrightarrow S = y.

  • From Q→RQ \to R paths: x+(3×4)+4y=27  ⟹  x+4y=15x + (3 \times 4) + 4y = 27 \implies x + 4y = 15.

  • From P→SP \to S paths: (3×4)+4y+3xy=62  ⟹  4y+3xy=50(3 \times 4) + 4y + 3xy = 62 \implies 4y + 3xy = 50.

  • Shortcut factor inspection: Rewrite as y(4+3x)=50y(4 + 3x) = 50. Since xx and yy are positive integers, (4+3x)(4 + 3x) must be a factor of 5050 greater than 4.

  • The factors of 50 are 1,2,5,10,25,501, 2, 5, 10, 25, 50:

    • 4+3x=25  ⟹  3x=21  ⟹  x=74 + 3x = 25 \implies 3x = 21 \implies x = 7 (gives y=2y = 2).

    • Quick check in x+4y=15x + 4y = 15: 7+4(2)=157 + 4(2) = 15 (perfect match!).

  • Answer: 7.

Detailed explanation

Concept: Counting Principles & Systematic Route Enumeration in Networks.

  1. Let the unknown number of direct paths between QQ and RR be xx, and between RR and SS be yy.

  2. From the problem statement, the known direct paths are:

    • P↔Q=3P \leftrightarrow Q = 3

    • Q↔S=4Q \leftrightarrow S = 4

    • P↔R=4P \leftrightarrow R = 4

    • P↔S=0P \leftrightarrow S = 0

  3. Enumerate all allowed paths from PP to SS (total = 62):

    • Path 1 (P→Q→SP \to Q \to S): 3×4=123 \times 4 = 12 ways

    • Path 2 (P→R→SP \to R \to S): 4×y=4y4 \times y = 4y ways

    • Path 3 (P→Q→R→SP \to Q \to R \to S): 3×x×y=3xy3 \times x \times y = 3xy ways

    • Setting up the first equation: 12+4y+3xy=62  ⟹  4y+3xy=50  ⟹  y(4+3x)=5012 + 4y + 3xy = 62 \implies 4y + 3xy = 50 \implies y(4 + 3x) = 50.

  4. Enumerate all allowed paths from QQ to RR (total = 27):

    • Path 1 (Directly Q→RQ \to R): xx ways

    • Path 2 (Q→P→RQ \to P \to R): 3×4=123 \times 4 = 12 ways

    • Path 3 (Q→S→RQ \to S \to R): 4×y=4y4 \times y = 4y ways

    • Setting up the second equation: x+12+4y=27  ⟹  x+4y=15  ⟹  4y=15−xx + 12 + 4y = 27 \implies x + 4y = 15 \implies 4y = 15 - x.

  5. Solve the system of equations simultaneously:

    • Express yy in terms of xx: y=15−x4y = \frac{15 - x}{4}.

    • Substitute yy into y(4+3x)=50y(4 + 3x) = 50:

      15−x4(4+3x)=50\frac{15 - x}{4}(4 + 3x) = 50

      (15−x)(4+3x)=200(15 - x)(4 + 3x) = 200

      60+45x−4x−3x2=20060 + 45x - 4x - 3x^2 = 200

      3x2−41x+140=03x^2 - 41x + 140 = 0

  6. Factorize the quadratic equation:

    (x−7)(3x−20)=0(x - 7)(3x - 20) = 0

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

  7. Verify yy: y=15−74=2y = \frac{15 - 7}{4} = 2, and 2(4+3(7))=2(25)=502(4 + 3(7)) = 2(25) = 50.

  8. The number of direct paths between QQ and RR is 77.

Practise similar questions

Practice 1 CAT_2024_SLOT2_QA_Q18_SQ01

A, B, C and D are four coastal ports. Cargo ships can travel between A and B along 2 direct sea routes, between B and D along 3 direct sea routes, and between A and C along 4 direct sea routes. There is no direct sea route between A and D, while there are a few direct sea routes between B and C, and between C and D. A cargo ship can travel from A to D either via B, or via C, or via B followed by C, respectively, in exactly 26 possible routes. A cargo ship can also travel from B to C either directly, or via A, or via D, in exactly 17 possible routes. Then, the number of direct sea routes between B and C is

Type-in-the-answer (TITA) question: no options are given; enter the value.

Show answer and solution

Answer:

3

Solution

  • Let direct paths between B and C be xx, and between C and D be yy.

  • From routes between B and C: x+(2×4)+3y=17  ⟹  x+3y=9  ⟹  x=9−3yx + (2 \times 4) + 3y = 17 \implies x + 3y = 9 \implies x = 9 - 3y.

  • From routes between A and D: (2×3)+4y+2xy=26  ⟹  4y+2xy=20  ⟹  y(2+x)=10(2 \times 3) + 4y + 2xy = 26 \implies 4y + 2xy = 20 \implies y(2 + x) = 10.

  • Substitute x=9−3yx = 9 - 3y: y(11−3y)=10  ⟹  3y2−11y+10=0y(11 - 3y) = 10 \implies 3y^2 - 11y + 10 = 0.

  • Factor: (3y−5)(y−2)=0  ⟹  y=2(3y - 5)(y - 2) = 0 \implies y = 2 (since yy must be an integer).

  • Find xx: x=9−3(2)=3x = 9 - 3(2) = 3.

  • Answer: 3.

Practice 2 CAT_2024_SLOT2_QA_Q18_SQ02

W, X, Y and Z are four regional railway stations. A train can travel between W and X along 3 direct rail tracks, between X and Z along 4 direct rail tracks, and between W and Y along 3 direct rail tracks. There is no direct rail track between W and Z, while there are a few direct rail tracks between X and Y, and between Y and Z. A passenger can travel from W to Z either via X, or via Y, or via X followed by Y, respectively, in exactly 48 possible ways. A passenger can also travel from X to Y either directly, or via W, or via Z, in exactly 22 possible ways. Then, the number of direct rail tracks between X and Y is

Type-in-the-answer (TITA) question: no options are given; enter the value.

Show answer and solution

Answer:

5

Solution

  • Let direct tracks between X and Y be xx, and between Y and Z be yy.

  • From routes between X and Y: x+(3×3)+4y=22  ⟹  x+4y=13  ⟹  x=13−4yx + (3 \times 3) + 4y = 22 \implies x + 4y = 13 \implies x = 13 - 4y.

  • From routes between W and Z: (3×4)+3y+3xy=48  ⟹  3y(1+x)=36  ⟹  y(1+x)=12(3 \times 4) + 3y + 3xy = 48 \implies 3y(1 + x) = 36 \implies y(1 + x) = 12.

  • Substitute x=13−4yx = 13 - 4y: y(14−4y)=12  ⟹  2y2−7y+6=0y(14 - 4y) = 12 \implies 2y^2 - 7y + 6 = 0.

  • Factor: (2y−3)(y−2)=0  ⟹  y=2(2y - 3)(y - 2) = 0 \implies y = 2 (integer root).

  • Find xx: x=13−4(2)=5x = 13 - 4(2) = 5.

  • Answer: 5.

Permutation & Combination questions from other CAT papers

  1. CAT 2025 Slot 1 Quant Q8
    A cafeteria offers 5 types of sandwiches. Moreover, for each type of sandwich, a customer can choose one of…
  2. CAT 2023 Slot 1 Quant Q21
    The number of all natural numbers up to 1000 with non-repeating digits is
  3. CAT 2022 Slot 1 Quant Q13
    The number of ways of distributing 20 identical balloons among 4 children such that each child gets some…
  4. CAT 2022 Slot 2 Quant Q11
    The number of integers greater than 2000 that can be formed with the digits 0, 1, 2, 3, 4, 5 , using each…
  5. CAT 2022 Slot 3 Quant Q3
    The arithmetic mean of all the distinct numbers that can be obtained by rearranging the digits in 1421 ,…

Practise this question with timing, notes and your mistake notebook.

Practise in PrepSoc