RU-ALLRUSSIAN 2006 Problem 108

A $3000\times 3000$ square is tiled by dominoes (i. e. $1\times 2$ rectangles) in an arbitrary way. Show that one can color the dominoes in three colors such that the number of the dominoes of each color is the same, and each dominoe $d$ has at most two neighbours of the same color as $d$. (Two dominoes are said to be neighbours if a cell of one domino has a common edge with a cell of the other one.)