Question

What is the smallest number of cells that need to be coloured in a 5 x 5 squareso that any 1 x 4 or 4 x 1 rectangle lying inside the square has at least one cell coloured?

(A) 5
(B) 6
(D) 8
(C) 7
(E) 9

Answer 1

(B) 6

Explanation:

You want the smallest number of cells in a 5×5 matrix that can be colored so that there are no 4 consecutive uncolored cells in any row or column.

Solution

The minimal coloring can be done any of 18 ways. Here is one of them:

`\left[\begin{array}{ccccc}\cdot&\square&\cdot&\cdot&\cdot\\\square&\cdot&\cdot&\cdot&\square\\\cdot&\cdot&\square&\cdot&\cdot\\\cdot&\cdot&\cdot&\square&\cdot\\\cdot&\square&\cdot&\cdot&\cdot\end{array}\right]`

Where each square represents a colored cell.

At least one cell on each edge must be colored (4). If those are arranged so that cells at each end of a row or column are colored, then that leaves two rows and two columns with no coloring. Two (2) additional cells are required to break up those into sections of 3 or less. That means a total of 6 cells must be colored to achieve the desired condition.