CAT 2018 Slot 1 DILR Q10
- Data Interpretation and Logical Reasoning
- Logical Reasoning › Grids
- Easy
- Type in the answer (TITA)
- CAT_2018_SLOT1_DILR_Q10
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 10
What is the minimum number of different numerals needed to fill a square matrix?
Type-in-the-answer (TITA) question: no options are given; enter the value.
Show answer and solution
Answer:
4
Solution
Concept: Chromatic Number Invariance, Planar Clique Bounds & Infinite Grid Periodic 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
• Scale Extension & Adjacency Graph Formulation:
• Expanding to a matrix gives 25 cells with degrees 3 (corners), 5 (edges), and 8 (interior).
• Finding the minimum numerals such that no adjacent cells share a numeral equals finding the chromatic number of the King's graph.
• Clique Upper Bound & Geometric Constraints:
• Any contiguous submatrix forms a complete subgraph , establishing .
• A 5-cell clique () is geometrically impossible:
• Pairwise adjacency requires Chebyshev distance $\le 1$ between all pairs.
• In a 2D grid, any set of mutually adjacent cells is confined within a $2 \times 2$ window.
• Any fifth cell outside this window has coordinate distance $\ge 2$ from at least one member, so $\omega(G) = 4$.
• 2D Periodic Tiling for the Grid:
• The parity assignment extends periodically across the entire grid:
$$f(r, c) = 2 \cdot ((r - 1) \bmod 2) + ((c - 1) \bmod 2) + 1$$
• Explicit configuration:
• Rows 1, 3, 5: $[1, 2, 1, 2, 1]$
• Rows 2, 4: $[3, 4, 3, 4, 3]$
• Identical numerals require and , forcing for distinct cells. Thus, no adjacent cells share a numeral.
• Option Matching / Numerical Answer:
• Expanding grid dimensions does not increase the chromatic number; 4 numerals remain sufficient.
• Confirms numerical TITA answer of .
Topper Take
• Matrix scaling trap: Increasing dimensions does not increase colors because the maximum clique size remains fixed.
• The periodic pattern tiles any grid seamlessly, confirming in under 30 seconds.
Other questions in this set
- Q9. What is the minimum number of different numerals needed to fill a 3 3 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…
- Q12. Suppose that all the cells adjacent to any particular cell must have different numerals. What is the minimum number of…
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