Browse by Stream
QnA
Home
QnA
Go To Your Study Dashboard

Get Answers to all your Questions

header-bg qa
  • Home
  • Management
  • 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

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:

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? 

 

 

Option: 1

9


Option: 2

16


Option: 3

4


Option: 4

25


Answers (1)

best_answer

We are given an n × n square matrix that needs to be populated with numerals in such a way that no two adjacent cells have the same numeral. Here, the term "adjacent" refers to cells that touch each other either horizontally, vertically, or diagonally. In the context of this problem, we need to consider the various cases of adjacent cells within the matrix.

The condition is provided that all cells adjacent to each other must have different numerals. To simplify the process, we start filling the matrix from the central square, which has the maximum number of adjacent squares (8). This allows us to focus on the central 9 squares. A minimum of 9 numbers will be required to fill these central squares.

           
  2 3 4  
  9 1 5  
  8 7 6  
         

Next, we proceed to fill the remaining squares, starting from the top-left square. We need to ensure that the 9 numbers we have are sufficient to fill all squares while maintaining the condition of no adjacent squares having the same number. Since none of the numbers in the second column are adjacent to the numbers 4, 5, or 6, we can choose any of these numbers to fill the top-left square.

Assuming we use 4 for the top-left square, we must consider the adjacency restrictions. Now, one of the cells with the number 4 becomes adjacent to the cell with the number 2, and no other cell adjacent to the 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 while adhering to the adjacency condition.

4 7 8    
5 2 3 4  
6 9 1 5  
  8 7 6  
         

Effectively, we are creating a grid around each of the numbers in the corners of the inner 3x3 matrix, ensuring that no adjacent cells have the same number. By following this approach and filling the remaining cells accordingly, we obtain one possible arrangement of the matrix.

4 7 8 6 7
5 2 3 4 9
6 9 1 5 2
3 8 7 6 8
2 5 4 3 9

Based on the given criteria, a minimum of 9 numbers is required to fill a 5x5 matrix while ensuring that no two adjacent cells contain the same value. 

Therefore, option 1 is the correct answer.

 

Posted by

Devendra Khairwa

View full answer

Similar Questions

Latest Question