CAT 2018 Slot 1 DILR Q9
- Data Interpretation and Logical Reasoning
- Logical Reasoning › Grids
- Easy
- Type in the answer (TITA)
- CAT_2018_SLOT1_DILR_Q09
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 9
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: Graph Coloring on King's Graph, Complete Subgraphs ( Cliques) & Parity-Based Grid 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
• King's Graph Formulation & Lower Bound ():
• Two cells and are adjacent if , defining a King's graph on a grid. Filling the matrix without identical adjacent numerals corresponds to proper vertex coloring.
• In any subgrid, such as , every pair of cells touches horizontally, vertically, or diagonally.
• This subgrid forms a 4-vertex clique (). Because no two adjacent vertices can share a numeral:
$$\chi(G) \ge \omega(G) \ge 4$$
• Hence, at least 4 distinct numerals are mathematically required.
• Explicit Construction Proving Sufficiency ():
• We verify that 4 numerals suffice via an alternating coordinate-parity tiling:
• Row 1: $[1, 2, 1]$
• Row 2: $[3, 4, 3]$
• Row 3: $[1, 2, 1]$
• Adjacency verification across all contacts:
• Orthogonal neighbors: horizontal pairs $(1,2)$ and $(3,4)$, and vertical pairs $(1,3)$ and $(2,4)$, are distinct.
• Diagonal neighbors: diagonal pairs $(1,4)$ and $(2,3)$ are distinct.
• Identical numerals appear only when both row and column parities match, requiring coordinate separation . Thus, identical numerals never touch.
• Option Matching / Numerical Answer:
• The theoretical lower bound of 4 is attained by the explicit valid construction.
• Confirms numerical TITA answer of .
Topper Take
• Spotting the clique () immediately yields the lower bound of 4 in 10 seconds.
• The repeating block proves sufficiency for any grid, making this an instant 30-second TITA mark.
Other questions in this set
- 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…
- 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