Tile the infinite plane with hexagons. Colour the hexagons black or white in any way you like, provided there is no line of three hexagons all the same colour. How many such colourings are there?

Obviously the answer is infinite. It increases exponentially with the area covered by the hexagons. My question is: how fast?

An altenative way to express the answer is in bits per hexagon, i.e. how much binary data can I store per hexagon on average.

No triangles

Note that three hexagons sharing a vertex cannot all be the same colour, otherwise there will be a line of three somewhere nearby.

Lower bound

Colour the hexagons red, green and blue such that neighbouring hexagons are coloured differently (this colouring is unique up to reflections). Then recolour the red ones black, the green ones white, and the blue ones at random. This always gives a legal colouring.

Not all legal colourings are of this special form. However, just considering colourings of this special form, the information density is $1/3$ (in bits/hexagon). This gives a lower bound on the true information density.

Upper bound

Cut the plane into parallel strips, each two hexagons wide. Colour each strip independently of the others, avoiding lines of three and triangles. Then put them back together. All legal colourings can be made in this way.

Not all colourings made this way are legal. However, considering all such colourings, the information density is about 0.551. This gives an upper bound on the true information density.

The figure of 0.551 can be computed by considering adding one hexagon at a time to the end of a semi-infinite two-wide strip. This gives a finite state machine with four states. Counting the number of paths of length $n$ from some arbitrary initial state to each final state gives a recurrence relation: $A_n = A_{n-2} + A_{n-3} + A_{n-4}$. For large $n$, $A_n \sim 1.4655^n$, and $log_2(1.4655) = 0.551$.

Update 2017-05-05 @mercio studied strips of width three and four and thereby found upper bounds of $0.472$ and $0.437$.


These are all the techniques I know for studying this problem. With considerable labour I know I could improve both bounds using these techniques, but really I need a new technique. Can you help?

  • 3
    $\begingroup$ Interesting problem. Perhaps you'd get more attention with some alternative equivalent statement (and tags). If I'm not mistaken, what you want is to count/bound the configurations on a triangular binary lattice such that no three consecutive points (in a row ) have the same value. No need to mention "information" (or even tiling). $\endgroup$ – leonbloy Apr 5 '17 at 13:06
  • 1
    $\begingroup$ I can't really judge what wording/tags will get the most attention. Mine would get mine. I'm happy to accept advice. What would you suggest? $\endgroup$ – apt1002 Apr 5 '17 at 13:55
  • 1
    $\begingroup$ This is out of my area of expertise, but I wonder if it would help you to have an algorithm for laying out the hexagons in a spiral pattern. That way you could probably develop an algorithm for the nearest neighbors. $\endgroup$ – Cye Waldman Apr 30 '17 at 18:36
  • 2
    $\begingroup$ by considering strips of width 3 and 4, I get upper bounds of 0.472 and 0.437. I'm a bit uncertain on how to systematically improve the lower bound. $\endgroup$ – mercio May 3 '17 at 10:40
  • 1
    $\begingroup$ This might be interesting: www3.nd.edu/~mtns/papers/80_2.pdf $\endgroup$ – leonbloy May 6 '17 at 16:37

Just a note (after the bounty expired) for the sake of future visitors:

Papers like "Bounds on the capacity of constrained two-dimensional codes" ( Forchhammer & Justesen, IEEE Transactions on Information Theory, 2000) and On the Capacity of 2-D Constrained Codes and Consequences for Full-Surface Data Channels (W. Weeks, 2012) and references cited therein could be a starting point. We could regard our hexagonal grid as a square grid and add run-length restrictions on diagonals.

Nevertheles, it seems hopeless to look for closed form solutions, but bounds and algorithms for estimating the capacity would be nice.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.