# If there is any colouring then there is periodic colouring.

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?

-

## 1 Answer

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.

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