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 n×nn \times n 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?

  1. A

    4

    Answer A in PrepSoc practice
  2. B

    16

    Answer B in PrepSoc practice
  3. C

    9

    Answer C in PrepSoc practice
  4. D

    25

    Answer D in PrepSoc practice

Answer this questionOr tap an option. Opens in practice mode, free, no sign-in.

Show answer and solution

Answer: (A)

4

Solution

Concept: Graph Defect Coloring, Pigeonhole Principle on Disjoint Cliques & Chromatic Robustness

Master State Table

Cell Type & PositionMatrix CoordinatesNeighbor CountContact BreakdownSubgrid Clique Invariant
Corner Cells4 vertices: (1,1),(1,n),(n,1),(n,n)(1,1), (1,n), (n,1), (n,n)3 neighbors2 orthogonal + 1 diagonalBelongs to 1 unique 2×22 \times 2 subgrid (K4K_4 clique)
Edge / Border CellsFirst/last row/col (non-corner)5 neighbors3 orthogonal + 2 diagonalBelongs to 2 overlapping 2×22 \times 2 subgrids
Interior CellsCentral rows & cols (2≤r,c≤n−12 \le r, c \le n-1)8 neighbors4 orthogonal + 4 diagonalBelongs to 4 overlapping 2×22 \times 2 subgrids
2×22 \times 2 Subgrid BlockAny contiguous 2×22 \times 2 cell window4 mutual neighborsPairwise adjacent across all 4 cellsMutual clique K4  ⟹  Minimum numerals ≥4K_4 \implies \text{Minimum numerals } \ge 4

Question Deduction

• Deconstructing the Relaxed Constraint:

• The problem allows at most one adjacent mistake across the entire 5×55 \times 5 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 2×22 \times 2 corner blocks in the 5×55 \times 5 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 K4K_4 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 K4K_4 blocks share no cells, their internal defects are completely disjoint.

• Coloring the grid with 3 numerals therefore produces at least 1+1+1+1=41 + 1 + 1 + 1 = 4 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 K4K_4 cliques demand at least 4 errors for 3 colors, making 4 mathematically airtight.

Other questions in this set

  1. Q9. What is the minimum number of different numerals needed to fill a 3 3 square matrix?
  2. Q10. What is the minimum number of different numerals needed to fill a 5 5 square matrix?
  3. 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

  1. CAT 2025 Slot 2 DILR Q6
    What was the total number of pings made by B1, B2, and B3?
  2. CAT 2025 Slot 2 DILR Q7
    Which of the following statements about the relative sizes of the balls is NOT NECESSARILY true?
  3. CAT 2025 Slot 2 DILR Q8
    Which of the following statements about the relative sizes of the hoops is true?
  4. CAT 2025 Slot 2 DILR Q9
    What BEST can be said about the total number of pings from all the tests undertaken?
  5. CAT 2025 Slot 3 DILR Q10
    What was the duration of calls (in minutes) from Bijay to Anu?

Practise this question with timing, notes and your mistake notebook.

Practise in PrepSoc