CAT 2018 Slot 1 DILR Q12

  • Data Interpretation and Logical Reasoning
  • Logical Reasoning › Grids
  • Easy
  • Multiple choice
  • CAT_2018_SLOT1_DILR_Q12

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 12

Suppose that all the cells adjacent to any particular cell must have different numerals. What is the minimum number of different numerals needed to fill a 5×55 \times 5 square matrix?

  1. A

    25

    Answer A in PrepSoc practice
  2. B

    4

    Answer B in PrepSoc practice
  3. C

    16

    Answer C in PrepSoc practice
  4. D

    9

    Answer D in PrepSoc practice

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

Show answer and solution

Answer: (D)

9

Solution

Concept: Locally Injective Neighborhood Coloring, Square Graph Distance Constraints & 3×33 \times 3 Modulo 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

• Neighborhood Exclusivity & Lower Bound (≥9\ge 9):

• The rule requires that for every cell vv, all adjacent cells in its neighborhood N(v)N(v) must have pairwise distinct numerals (f(u1)≠f(u2)f(u_1) \ne f(u_2) for u1≠u2∈N(v)u_1 \ne u_2 \in N(v)).

• Consider central cell (3,3)(3, 3): its 8 adjacent neighbors form N(3,3)N(3,3), requiring 8 distinct numerals.

• Central cell (3,3)(3, 3) cannot share a numeral with any neighbor u∈N(3,3)u \in N(3,3): any neighbor uu shares a mutual neighbor ww with (3,3)(3, 3) (e.g., u=(2,3)u=(2,3) and (3,3)(3,3) both touch w=(2,2)w=(2,2)). If f(3,3)=f(u)f(3,3) = f(u), then N(w)N(w) contains duplicate numerals, violating the rule at ww.

• Hence, all 9 cells in the 3×33 \times 3 block must have distinct numerals, establishing a lower bound of 9.

• Explicit Periodic Construction Proving Sufficiency:

• We tile the 5×55 \times 5 matrix using a modulo-3 periodic assignment:

$$f(r, c) = 3 \cdot ((r - 1) \bmod 3) + ((c - 1) \bmod 3) + 1$$

• Rows 1, 4: [1,2,3,1,2][1, 2, 3, 1, 2]; Rows 2, 5: [4,5,6,4,5][4, 5, 6, 4, 5]; Row 3: [7,8,9,7,8][7, 8, 9, 7, 8].

• Any cell's neighborhood lies within its local 3×33 \times 3 window. Because every 3×33 \times 3 window contains all 9 distinct pairs of (r mod 3,c mod 3)(r \bmod 3, c \bmod 3), all neighbors of every cell receive pairwise distinct numerals.

• Option Matching / Numerical Answer:

• The lower bound of 9 matches the explicit periodic construction.

• Matches Option 4 ("9").

• Distractors fail: Options 1 ("25"), 2 ("4"), and 3 ("16") fail distinct-neighbor or minimality tests.

• Confirms Option 4 as the correct choice.

Topper Take

• Quick Mental Anchor: A central cell plus its 8 neighbors forms a 3×33 \times 3 block of 9 mutually conflicting cells, fixing the lower bound to 9 in 20 seconds.

• Period-3 tiling [1..9][1..9] covers the grid without conflicts, immediately confirming Option 4.

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. Q11. Suppose you are allowed to make one mistake, that is, one pair of adjacent cells can have the same numeral. What is…

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