1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .