CAT 2018 Slot 1 DILR Question & Solution

Logical ReasoningMedium

Data Set

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 1

What is the minimum number of different numerals needed to fill a 3×3 square matrix?

Solution:

Let us use 1 to denote the first number that we fill. We have to fill as many squares with 1 as possible. If we start with the top-left square, we can fill 4 squares with the number 1.

Now, we can fill number 2 only in 2 of the 5 squares available.

The 3 squares available now are adjacent to each other. Therefore, we will require at least 2 numbers to fill these squares.

We need a minimum of 4 numbers to fill a 3x3 square matrix such that no 2 adjacent cells contain the same number. Therefore, 4 is the correct answer.

Question 2

What is the minimum number of different numerals needed to fill a 5×5 square 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.

As we can see, a minimum of 4 numbers are required to fill a 5x5 matrix. Therefore, 4 is the correct answer.

Question 3

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.

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.

Question 4

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.