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

What is the minimum number of different numerals needed to fill a 5×55 \times 5 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: Chromatic Number Invariance, Planar Clique Bounds & Infinite Grid Periodic 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

• Scale Extension & Adjacency Graph Formulation:

• Expanding to a 5×55 \times 5 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 χ(G)\chi(G) of the 5×55 \times 5 King's graph.

• Clique Upper Bound & Geometric Constraints:

• Any contiguous 2×22 \times 2 submatrix forms a complete subgraph K4K_4, establishing χ(G)≥ω(G)≥4\chi(G) \ge \omega(G) \ge 4.

• A 5-cell clique (K5K_5) 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 5×55 \times 5 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 5×55 \times 5 configuration:

• Rows 1, 3, 5: $[1, 2, 1, 2, 1]$

• Rows 2, 4: $[3, 4, 3, 4, 3]$

• Identical numerals require r1≡r2(mod2)r_1 \equiv r_2 \pmod 2 and c1≡c2(mod2)c_1 \equiv c_2 \pmod 2, forcing max⁡(∣r1−r2∣,∣c1−c2∣)≥2\max(\vert r_1 - r_2 \vert, \vert c_1 - c_2 \vert) \ge 2 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 44.

Topper Take

• Matrix scaling trap: Increasing dimensions does not increase colors because the maximum clique size ω=4\omega = 4 remains fixed.

• The 2×22 \times 2 periodic pattern tiles any n×nn \times n grid seamlessly, confirming χ=4\chi = 4 in under 30 seconds.

Other questions in this set

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