CAT 2024 Slot 2 DILR Q8

  • Data Interpretation and Logical Reasoning
  • Logical Reasoning › Grids
  • Hard
  • Type in the answer (TITA)
  • CAT_2024_SLOT2_DILR_Q08

Data set · questions 6–9

Diagram

The above is a schematic diagram of walkways (indicated by all the straight lines) and lakes (3 of them, each in the shape of rectangles - shaded in the diagram) of a gated area. Different points on the walkway are indicated by letters (A through P) with distances being OP = 150 m, ON = MN = 300 m, ML = 400 m, EL = 200 m, DE = 400 m.

The following additional information about the facilities in the area is known.

  1. The only entry/exit point is at C.
  2. There are many residences within the gated area; all of them are located on the path AH and ML with four of them being at A, H, M, and L.
  3. The post office is located at P and the bank is located at B.

Question 8

One resident takes a walk within the gated area starting from A and returning to A without going through any point (other than A) more than once. What is the maximum distance (in m) she can walk in this way?

□\square

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:

5100

Solution

Concept: Hamiltonian Cycle Construction / Longest Simple Cycle in Grid Networks

Master State Table

Segment CategoryPathway SegmentsLength (m)Structural Description / Topological Role
Horizontal (East-West)AB∥HG∥IJ∥POAB \parallel HG \parallel IJ \parallel PO150150Left corridor width (OP=150 mOP = 150\text{ m})
BC∥GF∥JK∥ONBC \parallel GF \parallel JK \parallel ON300300Central corridor width (ON=300 mON = 300\text{ m}, Lake 2 top/bottom)
CD∥FE∥KL∥NMCD \parallel FE \parallel KL \parallel NM300300Right corridor width (MN=300 mMN = 300\text{ m}, Lakes 1 & 3 top/bottom)
Vertical (North-South)AH∥BG∥CF∥DEAH \parallel BG \parallel CF \parallel DE400400Top tier height (DE=400 mDE = 400\text{ m}, Lake 1 east/west)
HI∥GJ∥FK∥ELHI \parallel GJ \parallel FK \parallel EL200200Middle tier height (EL=200 mEL = 200\text{ m}, Lake 2 east/west)
IP∥JO∥KN∥LMIP \parallel JO \parallel KN \parallel LM400400Bottom tier height (ML=400 mML = 400\text{ m}, Lake 3 east/west)
Diagonal HypotenuseIGIG250250Shortcut across ΔIHJ\Delta IHJ / ΔIGJ\Delta IGJ (1502+2002=250 m\sqrt{150^2 + 200^2} = 250\text{ m})
OKOK500500Shortcut across ΔONK\Delta ONK (3002+4002=500 m\sqrt{300^2 + 400^2} = 500\text{ m})

Question Deduction

• Objective & Topological Constraints:

  • The resident starts at AA and returns to AA without visiting any vertex (other than AA) more than once.

  • This specifies a simple cycle in the planar graph. The objective is to maximize total distance.

• Maximization Principles:

  • Vertex Saturation: A simple cycle can visit at most the total number of distinct vertices in the graph (1616 vertices, AA through PP).

  • Perimeter Preference Over Diagonals: By the triangle inequality, rectangular boundary paths are strictly longer than diagonal shortcuts (IJ+JG=350 m>IG=250 mIJ + JG = 350\text{ m} > IG = 250\text{ m}; ON+NK=700 m>OK=500 mON + NK = 700\text{ m} > OK = 500\text{ m}). Thus, an optimal longest cycle must use strictly grid-aligned segments.

• Construction of Full 16-Vertex Hamiltonian Cycle:

  • We construct a simple cycle that weaves through every single vertex of the 16-node network:

    A→B→G→F→C→D→E→L→M→N→K→J→O→P→I→H→AA \to B \to G \to F \to C \to D \to E \to L \to M \to N \to K \to J \to O \to P \to I \to H \to A

  • Verification: Every vertex from AA to PP is visited exactly once, closing at AA, with zero self-intersections.

• Segment-by-Segment Length Aggregation:

\text{Total Distance} &= AB + BG + GF + FC + CD + DE + EL + LM \\ &\quad + MN + NK + KJ + JO + OP + PI + IH + HA \\ &= 150 + 400 + 300 + 400 + 300 + 400 + 200 + 400 \\ &\quad + 300 + 400 + 300 + 400 + 150 + 400 + 200 + 400 \\ &= 5100\text{ m} \end{aligned}$$ - Since all $16$ vertices are exhausted and all traversed segments are maximal grid edges, $5100\text{ m}$ is the absolute global upper bound. ### Topper Take • **Hamiltonian Snaking**: Maximizing a simple cycle without vertex repetition requires consuming all 16 vertices while avoiding shorter hypotenuses. Snaking through the entire boundary and central rungs visits every node once, yielding $5100\text{ m}$ directly.

Other questions in this set

  1. Q6. One resident whose house is located at L, needs to visit the post office as well as the bank. What is the minimum…
  2. Q7. One person enters the gated area and decides to walk as much as possible before leaving the area without walking along…
  3. Q9. Visitors coming for morning walks are allowed to enter as long as they do not pass by any of the residences and do not…

Grids questions from other CAT papers

  1. CAT 2025 Slot 2 DILR Q6
    What was the total number of pings made by B1, B2, and B3?
  2. CAT 2025 Slot 2 DILR Q7
    Which of the following statements about the relative sizes of the balls is NOT NECESSARILY true?
  3. CAT 2025 Slot 2 DILR Q8
    Which of the following statements about the relative sizes of the hoops is true?
  4. CAT 2025 Slot 2 DILR Q9
    What BEST can be said about the total number of pings from all the tests undertaken?
  5. CAT 2025 Slot 3 DILR Q10
    What was the duration of calls (in minutes) from Bijay to Anu?

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

Practise in PrepSoc