Colouring the hex grid

by
Jan Kristian Haugland

Given a positive integer *n*, suppose each cell of the regular hexagonal grid is given one out
of 2*n*+1 available colours.

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 2*n*^{2} 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.