CAT 2018 Slot 1 DILR Q12
- Data Interpretation and Logical Reasoning
- Logical Reasoning › Grids
- Easy
- Multiple choice
- CAT_2018_SLOT1_DILR_Q12
Data set · questions 9–12
You are given an square matrix to be filled with numerals so that no two adjacent cells have the same numeral. Two cells are called adjacent if they touch each other horizontally, vertically or diagonally. So a cell in one of the four corners has three cells adjacent to it, and a cell in the first or last row or column which is not in the corner has five cells adjacent to it. Any other cell has eight cells adjacent to it.
Question 12
Suppose that all the cells adjacent to any particular cell must have different numerals. What is the minimum number of different numerals needed to fill a square matrix?
Show answer and solution
Answer: (D)
9
Solution
Concept: Locally Injective Neighborhood Coloring, Square Graph Distance Constraints & Modulo Tiling
Master State Table
| Cell Type & Position | Matrix Coordinates | Neighbor Count | Contact Breakdown | Subgrid Clique Invariant |
|---|---|---|---|---|
| Corner Cells | 4 vertices: | 3 neighbors | 2 orthogonal + 1 diagonal | Belongs to 1 unique subgrid ( clique) |
| Edge / Border Cells | First/last row/col (non-corner) | 5 neighbors | 3 orthogonal + 2 diagonal | Belongs to 2 overlapping subgrids |
| Interior Cells | Central rows & cols () | 8 neighbors | 4 orthogonal + 4 diagonal | Belongs to 4 overlapping subgrids |
| Subgrid Block | Any contiguous cell window | 4 mutual neighbors | Pairwise adjacent across all 4 cells | Mutual clique |
Question Deduction
• Neighborhood Exclusivity & Lower Bound ():
• The rule requires that for every cell , all adjacent cells in its neighborhood must have pairwise distinct numerals ( for ).
• Consider central cell : its 8 adjacent neighbors form , requiring 8 distinct numerals.
• Central cell cannot share a numeral with any neighbor : any neighbor shares a mutual neighbor with (e.g., and both touch ). If , then contains duplicate numerals, violating the rule at .
• Hence, all 9 cells in the block must have distinct numerals, establishing a lower bound of 9.
• Explicit Periodic Construction Proving Sufficiency:
• We tile the matrix using a modulo-3 periodic assignment:
$$f(r, c) = 3 \cdot ((r - 1) \bmod 3) + ((c - 1) \bmod 3) + 1$$
• Rows 1, 4: ; Rows 2, 5: ; Row 3: .
• Any cell's neighborhood lies within its local window. Because every window contains all 9 distinct pairs of , all neighbors of every cell receive pairwise distinct numerals.
• Option Matching / Numerical Answer:
• The lower bound of 9 matches the explicit periodic construction.
• Matches Option 4 ("9").
• Distractors fail: Options 1 ("25"), 2 ("4"), and 3 ("16") fail distinct-neighbor or minimality tests.
• Confirms Option 4 as the correct choice.
Topper Take
• Quick Mental Anchor: A central cell plus its 8 neighbors forms a block of 9 mutually conflicting cells, fixing the lower bound to 9 in 20 seconds.
• Period-3 tiling covers the grid without conflicts, immediately confirming Option 4.
Other questions in this set
- Q9. What is the minimum number of different numerals needed to fill a 3 3 square matrix?
- Q10. What is the minimum number of different numerals needed to fill a 5 5 square matrix?
- Q11. Suppose you are allowed to make one mistake, that is, one pair of adjacent cells can have the same numeral. What is…
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