In this question I try to colour infinite grid paper.

There are $k$ colours and $N$ patterns (pattern is a $2\times 2$ square that coloured some way). The colouring $C$ is called the "correct" if every $2\times 2$ square in it is a pattern.
Suppose that there is correct coloring on the infinite grid plane. It seems that in this case there is a periodic correct colouring (i.e. there are $u,v$ such that for any $x,y$ cells $(x,y), (x+u,y), (x, y+v) $ are coloured same way), but I failed to prove that.

Is it true?


No. Your correctness condition can be used to model sets of Wang tiles, and there are sets of Wang tiles that tile the plane only aperiodically.

  • 1
    $\begingroup$ Do you mean "aperiodically"? thanks! $\endgroup$ – Nikita Kalinin Dec 2 '10 at 21:46
  • $\begingroup$ Oops, thanks for catching that typo. Fixed. $\endgroup$ – David Eppstein Dec 2 '10 at 22:04

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.