CAT 2018 Slot 1 DILR Q11
- Data Interpretation and Logical Reasoning
- Logical Reasoning › Grids
- Easy
- Multiple choice
- CAT_2018_SLOT1_DILR_Q11
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 11
Suppose you are allowed to make one mistake, that is, one pair of adjacent cells can have the same numeral. What is the minimum number of different numerals required to fill a 5×5 matrix?
Show answer and solution
Answer: (A)
4
Solution
Concept: Graph Defect Coloring, Pigeonhole Principle on Disjoint Cliques & Chromatic Robustness
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
• Deconstructing the Relaxed Constraint:
• The problem allows at most one adjacent mistake across the entire matrix.
• We evaluate whether this single permissible defect allows filling the grid using fewer than 4 numerals (e.g., 3 numerals).
• Disjoint Clique Partitioning via Pigeonhole Principle:
• Consider four mutually vertex-disjoint corner blocks in the grid:
• Blocks at rows $\{1,2\} \times \{1,2\}$, $\{1,2\} \times \{4,5\}$, $\{4,5\} \times \{1,2\}$, and $\{4,5\} \times \{4,5\}$.
• Each block is an independent complete subgraph of 4 pairwise adjacent cells.
• By the Pigeonhole Principle, assigning 3 numerals to any 4-clique forces at least two cells within that block to share a numeral, incurring at least 1 adjacent mistake per block.
• Defect Count Contradiction & Sufficiency of 4:
• Because these four blocks share no cells, their internal defects are completely disjoint.
• Coloring the grid with 3 numerals therefore produces at least distinct mistakes.
• Since only 1 mistake is allowed, 3 numerals are strictly impossible.
• Because 4 numerals achieve a valid configuration with zero mistakes, 4 numerals naturally satisfy the relaxed rule.
• Option Matching / Numerical Answer:
• Option 1 specifies "4", matching the derived minimum.
• Distractors fail: Options 2 ("16"), 3 ("9"), and 4 ("25") are far larger than the achievable minimum of 4.
• Confirms Option 1 as the correct choice.
Topper Take
• MCQ Elimination Hack: Options are 4, 16, 9, 25. Since 4 numerals work with 0 mistakes, relaxing the rule cannot require more than 4 colors. 4 is the smallest choice, solved in 10 seconds.
• Four disjoint cliques demand at least 4 errors for 3 colors, making 4 mathematically airtight.
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?
- 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