Singapore Mathematical Olympiad (SMO)

The maximum value is $k=20000$. Define a region as a maximal set of same-colour squares such that there is a path of the same colour between any $2$ squares in the region. From the first condition, there is exactly one marked square in a region and so there are $k$ regions. Two regions are neighbours if they have a vertex in common.

Now suppose that $k>20000$. Form a graph whose vertices are the regions and whose edges join neighbouring regions. Since there are only $2000$ colours, there are $2$ regions $P,Q$ with the same colour. Thus there is a path $P=A_0,A_1,\dots ,A_i=Q$, with $i\ge 2000$ by the second condition. Consider the longest path in the graph: $B_0,B_1,\dots ,B_j$. Then $j\ge i\ge 2000$. Suppose there is a vertex $C$ not in the path but is adjacent to a vertex $B_k$ in the path. Then $k\ne 0,j$, else there is a longer path. Consider the $2001$ vertices $C,B_p,B_{p+1},\dots ,B_{p+1999}$ where $p<k<p+1999\le j$. Two of them have the same colour but their distance apart is $<2000$, contradicting the second condition. So $B_0,B_1,\dots ,B_j$ are all the regions and $j=k-1$. Thus to move from a square in $B_m$ to a square in $B_{m+x}$, where the index is taken mod $k$, at least $x$ moves or $k-x$ moves (if $m+x>k$) are needed. (Here a move is moving from a square to a neighbouring square.) Also $2$ neighbouring squares belong to the same region or $2$ adjacent regions.

Let $X$ be the $2\times 2$ square in the centre of the grid. Since the $4$ squares in $X$ are mutually adjacent, $X\subseteq B_m\cup B_{m+1}$ for some $m$. Take $Y\in B_{m+\lfloor (k+1)/2\rfloor }$. Suppose the square in $X$ that is nearest to $Y$ can move to $Y$ in a minimum number of $s$ moves. Then, since that square can be in $B_m$ or $B_{m+1}$, $9999\ge m\ge \lfloor (k-1)/2\rfloor$ or $20000\ge k$.

There is a colouring that gives $20000$ regions. Colour all the squares in row $i$ with colour $j$ if $i\equiv j(\mathrm{mod}2000)$.