Q8 Matemática  (Middle European Mathematical Olympiad 2009)

Colorimos cada quadrado do tabuleiro $2009$ x $2009$ com uma das cores $n$ (não precisamos usar todas as cores). Uma cor é dita conectada se houver apenas uma casa dessa cor ou duas casas quaisquer da cor puderem ser alcançadas uma da outra por uma sequência de lances de uma dama de xadrez sem paradas intermediárias em casas de outra cor (uma quen de xadrez se move horizontal, vertical ou diagonal). Encontre o máximo $n$, de modo que para cada coloração do tabuleiro pelo menos uma cor presente no tabuleiro seja conectada.