
4. Consider $n^{2}$ unit squares in the $x y$-plane centred at point $(i, j)$ with integer coordinates, $1 \leq i \leq n, 1 \leq j \leq n$. It is required to colour each unit square in such a way that whenever $1 \leq i<j \leq n$ and $1 \leq k<l \leq n$, the three squares with centres at $(i, k),(j, k),(j, l)$ have distinct colours. What is the least possible number of colours needed?


Solution: We first show that at least $2 n-1$ colours are needed. Observe that squares with centres $(i, 1)$ must all have diffrent colours for $1 \leq i \leq n$; let us call them $C_{1}, C_{2}, \ldots, C_{n}$. Besides, the squares with centres $(n, j)$, for $2 \leq j \leq n$ must have different colours and these must be different from $C_{1}, C_{2}, \ldots, C_{n}$. Thus we need at least $n+(n-1)=2 n-1$ colours. The following diagram shows that $2 n-1$ colours will suffice.

![](https://cdn.mathpix.com/cropped/2024_06_05_48f517a68bfec8a04d11g-3.jpg?height=547&width=575&top_left_y=797&top_left_x=691)
