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 other horizontally, vertica

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 you are allowed to make one mistake, that is, one pair of adjacent cells can have the same numeral. What is the minimum number of different numerals required to fill a 5×5 matrix?

Option: 1

16


Option: 2

4


Option: 3

25


Option: 4

9


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.

Consider a 5x5 matrix where we begin filling from the top-left square with the number 1, aiming to utilize as many squares as possible for this number.

1    1    1
         
1   1   1
         
1   1   1

To bridge the gap between two adjacent 1s, we introduce a second number, 2.

1 2 1 2 1
         
1 2 1 2 1
         
1 2 1 2 1

In rows 2 and 4, all cells are adjacent to those containing numbers 1 and 2. Consequently, rows 2 and 4 should be filled with a new set of numbers. To ensure that adjacent cells do not have the same number, we need a minimum of 2 distinct numbers for each row, alternating the numbers in consecutive cells. Remarkably, rows 2 and 4 are independent of each other, allowing us to employ the same set of numbers for both rows.

1 2 1 2 1
3 4 3 4 3
1 2 1 2 1
3 4 3 4 3
1 2 1 2 1

It is evident that a total of 4 numbers are required to fill the 5x5 matrix.

Additionally, the problem states that one mistake is allowed, meaning that one pair of adjacent cells can contain the same number. In the arrangement presented above, we can modify any value along the edge to satisfy this condition. For instance, the 2 in the bottom-most row can be changed to 4. Despite this alteration, the number of numbers required to fill the matrix remains 4.

 

 

Posted by

jitender.kumar

View full answer

Similar Questions

Trending Articles/News

anam-khan

CAT 2024 registration ends soon; MBA programmes offered by IIMs
anam-khan

CAT 2024: Older IIMs attract more students with work experience; engineers’ count falls
anam-khan

CAT 2024: IIM Calcutta warns of fraud registration website; urges candidates to report suspicious activity

Latest Question