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 45

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?

Solution

Let us consider a 5x5 matrix. Let us start with the top left square and fill number 1 in as many squares as possible. 

 We have to use a second number, 2 to fill the gap between two 1s. 

 All the cells in row 2 and row 4 are adjacent to the cells containing numbers 1 and 2. Therefore, rows 2 and 4 should be filled with a new set of numbers. We need at least 2 numbers to fill a row such that the adjacent cells do not contain the same number (by alternating the numbers in the consecutive cells). Rows 2 and 4 are completely isolated from each other and hence, the same set of numbers can be used to fill both the rows.

4 numbers are required to fill a 5x5 matrix.
It has been given that we are allowed to make 1 mistake - One pair of adjacent cells can contain the same number. In the arrangement given above, we can alter any value along the edge to satisfy this condition. For example, the 2 in the bottom-most row can be changed to 4. Still, the number of numbers required to fill the matrix will be 4. 

Another way to approach this problem is as follows:
We know that a minimum of 4 numbers are required to fill a 5x5 matrix. If we are allowed to make a mistake, then the number of numbers required should either remain the same or go down. 4 is the smallest value among the given options. Therefore, we can be sure that even if we are allowed to make a mistake, 4 numbers will be required to fill the matrix and hence, option A is the right answer.

Video Solution

video

Create a FREE account and get:

  • All Quant CAT complete Formulas and shortcuts PDF
  • 38+ CAT previous year papers with video solutions PDF
  • 5000+ Topic-wise Previous year CAT Solved Questions for Free

cracku

Boost your Prep!

Download App