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 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 9

What is the minimum number of different numerals needed to fill a 3×3 3\times 3 square matrix?

Type-in-the-answer (TITA) question: no options are given; enter the value.

Answer this question Opens in practice mode, free, no sign-in.

Show answer and solution

Answer:

4

Solution

Concept: Graph Coloring on King's Graph, Complete Subgraphs (K4K_4 Cliques) & Parity-Based Grid Tiling

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

• King's Graph Formulation & Lower Bound (χ≥4\chi \ge 4):

• Two cells (r1,c1)(r_1, c_1) and (r2,c2)(r_2, c_2) are adjacent if max⁡(∣r1−r2∣,∣c1−c2∣)=1\max(\vert r_1 - r_2 \vert, \vert c_1 - c_2 \vert) = 1, defining a King's graph GG on a 3×33 \times 3 grid. Filling the matrix without identical adjacent numerals corresponds to proper vertex coloring.

• In any 2×22 \times 2 subgrid, such as {(1,1),(1,2),(2,1),(2,2)}\{(1,1), (1,2), (2,1), (2,2)\}, every pair of cells touches horizontally, vertically, or diagonally.

• This subgrid forms a 4-vertex clique (K4K_4). 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 (χ≤4\chi \le 4):

• We verify that 4 numerals {1,2,3,4}\{1, 2, 3, 4\} 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 ≥2\ge 2. 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 44.

Topper Take

• Spotting the 2×22 \times 2 clique (K4K_4) immediately yields the lower bound of 4 in 10 seconds.

• The repeating 2×22 \times 2 block [1,2;3,4][1, 2; 3, 4] proves sufficiency for any grid, making this an instant 30-second TITA mark.

Other questions in this set

  1. Q10. What is the minimum number of different numerals needed to fill a 5 5 square matrix?
  2. Q11. Suppose you are allowed to make one mistake, that is, one pair of adjacent cells can have the same numeral. What is…
  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