Skip to main contentSkip to solution

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.

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?

Solution

✅ Correct Option: 4

Lower bound: at least 99 numerals are necessary

Look at the central 3×33 \times 3 block and its centre ee with neighbors

(abcdefghi)\begin{pmatrix} a & b & c\\ d & e & f\\ g & h & i \end{pmatrix}

By the rule at ee, the eight neighbors {a,b,c,d,f,g,h,i}\{a,b,c,d,f,g,h,i\} must all be distinct (already 88 different numerals).

Now suppose ee shared a numeral with any neighbor, say e=ae=a. Consider the cell bb: its neighbor set includes both aa and ee, which would then have the same numeral — violating the requirement at bb that its neighbors be pairwise distinct. The same argument works for ee with any of the eight neighbors (there is always a cell adjacent to both).

Hence ee must also be different from each of its eight neighbors, forcing 99 distinct numerals in this 3×33 \times 3 block. Therefore the whole 5×55 \times 5 grid needs at least 99 numerals.


Upper bound: 99 numerals suffice (explicit construction)

Color cell (r,c)(r,c) by the pair (r mod 3,c mod 3)(r \bmod 3, c \bmod 3) mapped to the numerals {1,2,…,9}\{1,2,\dots,9\}. Concretely, use the repeating 3×33 \times 3 pattern

(123456789)\begin{pmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9 \end{pmatrix}

tiled across the 5×55 \times 5. Every 3×33 \times 3 block then contains all nine distinct numerals, so in particular the 88 neighbors around any centre are pairwise distinct. Edge and corner cells have fewer neighbors, which are a subset of some 3×33 \times 3 block and thus still pairwise distinct.


Conclusion

Both bounds match, so the minimum number of different numerals required is 9\boxed{9}.

Keyboard Shortcuts

  • Left arrow: Previous question
  • Right arrow: Next question
  • S key: Jump to solution
  • Q key: Jump to question