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? 



If there is any colouring then there is periodic colouring.
No. Your correctness condition can be used to model sets of [Wang tiles](http://en.wikipedia.org/wiki/Wang_tile), and there are sets of Wang tiles that tile the plane only aperiodically.


