In the diagram, each of the 15 small squares is going to be coloured. Any two squares that have a vertex in common or share a side must be a different colour. What is the least number of different colours needed?

![](https://cdn.mathpix.com/cropped/2024_04_20_6ed09463f225f8ba1f07g-123.jpg?height=154&width=247&top_left_y=1647&top_left_x=1378)
(A) 3
(B) 4
(C) 5
(D) 8
(E) 9
If we look at the top left four squares, we see that they must all be coloured a different colour, since they all have a vertex in common, so no two can be the same colour. So we need at least 4 colours. Can we colour the 15 squares with only 4 colours? If we try to do this, we can see that this is possible by taking a block of four squares, colouring the squares different colours, and shifting this block around the grid. (In the diagram, different numbers represent the four different colours.)

What would happen if the grid were bigger than 3 by 5 ?

Would 4 colours still be enough? This problem is related to a famous math problem called the "Four Colour Problem". Try looking this up on the Web!

| 1 | 2 | 1 | 2 | 1 |
| :--- | :--- | :--- | :--- | :--- |
| 3 | 4 | 3 | 4 | 3 |
| 1 | 2 | 1 | 2 | 1 |

#