Quatro cores são suficientes para colorir qualquer mapa

José Luiz Pastore Mello*
Especial para a Folha

No início do século 19, um jovem estudante inglês constatou que precisava de apenas quatro cores para colorir todos os distritos do mapa da Inglaterra de forma que os adjacentes tivessem sempre cores diferentes.

Tempos depois, intrigado com possíveis generalizações da sua conclusão para mapas com mais regiões, o jovem estudante escreveu para seu irmão no University College de Londres, perguntando se ele conhecia algum teorema que garantisse ser possível colorir um mapa qualquer com apenas quatro cores sem que regiões adjacentes ficassem com uma mesma cor (não se admite aqui a possibilidade de regiões com fronteira num só ponto).

O irmão não soube responder, mas levou o curioso problema ao conhecimento de um proeminente matemático da época, o professor DeMorgan, que, após alguns dias de investigação, mostrou-se incapaz de dar uma resposta definitiva ao problema, que, desde então, ficou conhecido como o problema das quatro cores e desafiou uma série de matemáticos profissionais e amadores por anos.

Apenas em 1976, Apel e Haken resolveram o problema de forma definitiva e completa, reduzindo todas as topologias de mapas a pouco mais de 2.000 casos distintos e, com a ajuda de computadores, demonstraram que quatro cores seriam suficientes para colorir qualquer tipo de mapa.

O trabalho de Apel e Haken teve importância histórica porque constituiu a primeira demonstração matemática feita por um computador (até hoje não se conhece uma demonstração do teorema das quatro cores que independa de verificações por computador!).

Agora que sabemos que quatro cores são suficientes para colorir um mapa, pergunto ao leitor: de quantas maneiras diferentes podemos colorir o mapa do Mercosul usando apenas quatro cores? (pense alguns minutos antes de prosseguir a leitura).

Se você respondeu 24 (ou quatro), caiu em armadilha; a resposta correta é 48. Aplicando corretamente o processo multiplicativo de contagem, observe que podemos usar quatro cores para o Brasil; para cada uma dessas cores podemos usar três para o Paraguai, duas para a Argentina e duas para o Uruguai, totalizando 48 possibilidades de mapas diferentes.