Q5 Matemática (Tournament Of Towns 1984)
Uma folha quadrada infinita é dada, com quadrados de lado . A “distância” entre duas casas é definida como o comprimento do caminho mais curto de uma dessas casas para a outra se movendo entre elas como uma torre de xadrez (medida ao longo da trajetória do centro da torre). Determine o número mínimo de cores com as quais é possível colorir a folha (a cada quadrado é dada uma única cor) de modo que cada par de quadrados com distância entre eles igual a $ 6 unidades receba cores diferentes. Dê um exemplo de tal coloração e prove que usando um número menor de cores não podemos atingir esse objetivo. (AG Pechkovskiy, IV Itenberg)