Q6 Matemática  (Baltic Way 2010)

Um tabuleiro $n\times n$ é colorido em $n$ cores de tal forma que a diagonal principal (do canto superior esquerdo ao canto inferior direito) é colorida na primeira cor; as duas diagonais adjacentes são coloridas na segunda cor; as duas diagonais seguintes (uma de cima e outra de baixo) são coloridas na terceira cor, etc; os dois cantos (superior direito e inferior esquerdo) são coloridos na cor $n$-th. Acontece que é possível colocar no tabuleiro $n$ torres, não havendo duas torres se atacando e de modo que não haja duas torres sobre células da mesma cor. Prove que $n=0(\mathrm{mod}4)$ ou $n=1(\mathrm{mod}4)$.