Let h(n) denote the smallest possible value (if any) of the maximal number of cells in any connected component induced by any n of
the colours. We have h(2) = 4, and this is attained by essentially only two distinct colourings. Click on the images for "edit mode".
In the case n = 3, there is a colouring that yields a maximum of 9 cells.
Is it optimal? Is it unique? I have verified that h(3) ≥ 8; i.e., h(3) ∈ {8, 9}.
An example that yields h(4) ≤ 24 is shown here.
If we instead consider the square grid, and assume that two cells must have a common edge in
order to be considered adjacent, then it is relatively easy to attain 2n2 cells for n out of n+1 colours.
Here is the case n = 3, and the reader should be able to spot the pattern for the general case.
