Bear and Three Colours

Limak, a little polar bear, loves puzzles. He has recently found an especially interesting one. There is a rectangular grid with N rows and N columns, both numbered 1 through N. Two cells are called adjacent if they share a side, i.e. all the cells other than those at boundary will have 4 adjacent cells. Every cell is colored in one of three colors. For convenience, let us label these colors by