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
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.
- The only entry/exit point is at C.
- 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.
- 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?
Type-in-the-answer (TITA) question: no options are given; enter the value.
Show answer and solution
Answer:
5100
Solution
Concept: Hamiltonian Cycle Construction / Longest Simple Cycle in Grid Networks
Master State Table
| Segment Category | Pathway Segments | Length (m) | Structural Description / Topological Role |
|---|---|---|---|
| Horizontal (East-West) | Left corridor width () | ||
| Central corridor width (, Lake 2 top/bottom) | |||
| Right corridor width (, Lakes 1 & 3 top/bottom) | |||
| Vertical (North-South) | Top tier height (, Lake 1 east/west) | ||
| Middle tier height (, Lake 2 east/west) | |||
| Bottom tier height (, Lake 3 east/west) | |||
| Diagonal Hypotenuse | Shortcut across / () | ||
| Shortcut across () |
Question Deduction
• Objective & Topological Constraints:
-
The resident starts at and returns to without visiting any vertex (other than ) 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 ( vertices, through ).
-
Perimeter Preference Over Diagonals: By the triangle inequality, rectangular boundary paths are strictly longer than diagonal shortcuts (; ). 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:
-
Verification: Every vertex from to is visited exactly once, closing at , 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
- Q6. One resident whose house is located at L, needs to visit the post office as well as the bank. What is the minimum…
- Q7. One person enters the gated area and decides to walk as much as possible before leaving the area without walking along…
- 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
- CAT 2025 Slot 2 DILR Q6
- CAT 2025 Slot 2 DILR Q7
- CAT 2025 Slot 2 DILR Q8
- CAT 2025 Slot 2 DILR Q9
- CAT 2025 Slot 3 DILR Q10
Practise this question with timing, notes and your mistake notebook.
Practise in PrepSoc