11
$\begingroup$

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$.

Summary

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?

$\endgroup$
16
  • 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, 2017 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, 2017 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$ Apr 30, 2017 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, 2017 at 10:40
  • 1
    $\begingroup$ This might be interesting: www3.nd.edu/~mtns/papers/80_2.pdf $\endgroup$
    – leonbloy
    May 6, 2017 at 16:37

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.