Q14 Matemática  (Tournament Of Towns 1998)

Qual é o número máximo de cores que podem ser usadas para pintar um tabuleiro de xadrez de modo que cada quadrado seja pintado em uma única cor e seja adjacente, horizontalmente, verticalmente, mas não diagonalmente, a pelo menos dois outros quadrados de seu própria cor? (A Shapovalov)