What is the smallest number of cells that need to be coloured in a 5 × 5 square grid so that every 1 × 4 or 4 × 1 rectangle in the grid has at least one coloured cell?
A 5 B 6 C 7 D 8 E 9
B
For every 1 × 4 or 4 × 1 rectangle in the grid to have at least one coloured cell, there must be at least one coloured cell in every row and in every column. However, only one coloured cell in each row and column would not be sufficient as, for example, a coloured cell in the far right column and no other coloured cell in the same row as that cell would leave a 4 × 1 rectangle consisting of the other four cells in that row without a coloured cell in it. Hence, any row or column in which an end cell is coloured must have at least one more coloured cell in it. Therefore at least six cells must be coloured and the diagram shows that such an arrangement is possible. Note —many other arrangements of coloured cells also exist.
Be up-to-date with our recent updates, new problems and answers!
Ask about our courses and offerings, and we will help you choose what works best for you.
