Instructions

You are given an n×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×5 square matrix?

Solution

It has been given that all the cells adjacent to a cell must have different numerals. Let us start filling the matrix from the central square since the central square has the maximum number of squares adjacent to it (8) and it will be easier to work around the central 9 squares. A minimum of 9 numbers will be required to fill the central 9 squares.

Now we have to fill the remaining squares. Let us start with the top left square. We have to check whether the 9 numbers will be sufficient to fill all the squares such that no 2 squares adjacent to a square have the same number. We can use any of the 3 numbers 4, 5, and 6 to fill the top left square since none of the numbers in the second column are adjacent to these numbers.

Let us assume that we use 4 to fill the top left square. Now, one of the cells with the number 4 has become adjacent to the cell with number 2 and no other cell adjacent to cell with number 2 (in the second row and second column) can have 4 as its neighbour. Similarly, we can fill the first row with numbers 8 and 7.

In essence, we are trying to create a gird around each of the numbers in the corners of the inner 3x3 matrix such that no 2 cells adjacent to a cell have the same number. Filling the other cells similarly, we get the following matrix as one of the possible cases.

We need a minimum of 9 numbers to fill a 5x5 matrix such that for any cell, no 2 cells adjacent to it contain the same value. Therefore, option D is the right answer.

### Video Solution

• All Quant CAT complete Formulas and shortcuts PDF
• 35+ CAT previous year papers with video solutions PDF