Question 16
Colour a $20000 \times 20000$ square grid using $2000$ different colours with $1$ colour in each square. Two squares are neighbours if they share a vertex. A path is a sequence of squares so that $2$ successive squares are neighbours. Mark $k$ of the squares. For each unmarked square $x$, there is exactly $1$ marked square $y$ of the same colour so that $x$ and $y$ are connected by a path of squares of the same colour. For any $2$ marked squares of the same colour, any path connecting them must pass through squares of all the colours. Find the maximum value of $k$.