GK 2017 Q24
24. Ellen wants to colour some of the cells of a 4 × 4 grid. She wants to do this so that each coloured cell shares at least one side with an uncoloured cell and each uncoloured cell shares at least one side with a coloured cell.
What is the largest number of cells she can colour?
- A 12
- B 11
- C 10
- D 9
- E 8
Grey Kangaroo 2017, Question 24. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: A 12
Consider the four cells in the top left corner. It is not possible for all four cells to be coloured or the top left cell would not be touching an uncoloured cell and so there is at least one uncoloured cell in that group of four cells. By a similar argument, there is at least one uncoloured cell amongst the four cells in the bottom left corner, amongst the four cells in the bottom right corner and amongst the four cells in the top right corner. Therefore there are at least four uncoloured cells in the grid and hence at most twelve coloured cells. The diagram above shows that an acceptable arrangement is possible with twelve coloured cells.
Hence the largest number of cells Ellen can colour is twelve.
Solution © UK Mathematics Trust, from the GK 2017 solutions.