Arquivo da tag: Quatro cores

O teorema das cores

Rookie

Na coleção de meus teoremas favoritos, o teorema das cores tem um lugar especial. Eu trabalhava na usina nuclear de Belleville-sur-Loire quando o responsável de meu setor explicava as divisões e departamentos da central. Ele tomou uma planta dos principais encanamentos, aquecedores e turbinas e pôs-se a remarcar os setores da usina: os aquecedores primários, os secundários, a transmissão do reator às válvulas, o condensador, cada setor era marcado com uma cor, e setores vizinhos possuíam cores diferentes, para não causar confusão. Ele usava aqueles marcadores Stabilo coloridos, e, olhando para sua coleção de canetas, apenas quatro cores, disse: “acho que não vou ter canetas para marcar todos”. Quase eufórico, respondi: não, você vai!

Nenhum atlas que se preze tentaria um desenho tão minimalista dos mapas, em geral vemos países em várias cores e tons, e sempre temos aquela caixa de doze cores da Faber-Castell para colorir o papel-vegetal em nossas aulas de geografia na infância, o teorema, por isso, nem é tão famoso. Ainda, quatro cores colorem qualquer mapa, e esse resultado foi um dos de mais difícil demonstração na história da matemática.

Esse teorema, o das quatro cores, era conjecturado havia muito antes de sua demonstração, que é tida como uma das mais feias da matemática. Antes de comentar a prova, vamos comentar o teorema.

Esse teorema é apenas válido para mapas cujos países são conexos, ou seja, o caso do Alaska, parte dos EUA e desconexo do resto do país, não pode ser incluído. Com apenas regiões conexas, é fácil perceber que você precisa de ao menos quatro cores para colorir um mapa; é possível encontrar quatro países vizinhos uns dos outros de forma a exigir quatro cores. Temos, como exemplo simples, o Paraguai e Luxemburgo. Deste último, usando todas as minhas habilidades de cartografia, compus um pequeno diagrama de suas fronteiras: França, Alemanha e Bélgica. Esses três países fazem fronteira entre si e com Luxemburgo, preciso de quatro cores para pintar esse mapa:

Mas é completamente impossível, em um mapa plano ou em uma esfera, desenhar cinco países tais que todos fazem fronteiras com todos. Esse é um exercício divertido, tentar compor o mais estranho dos mapas e ir colorindo pouco a pouco, convencendo-se do teorema, tentando exigir uma quinta cor, e jamais precisando. A Wikipédia possui um exemplo interessante de mapa caótico, irreal e muito mais bagunçado que o de um atlas seria, e ainda conseguimos colori-lo com não mais que quatro cores.

A demonstração desse teorema é surpreendente. Abandonando os ideais de beleza matemáticos, a busca de uma prova elegante e concisa de um resultado tão bonito, dois matemáticos em 1961, Appel e Haken, demonstraram, grosso modo, que todas as situações de mapas planos que precisam ser coloridos caem em 1 de 1.936 casos. É isso mesmo: eles demonstraram, em um abuso de linguagem, que todo mapa não é mais que um caso levemente modificado ou composto de 1.936 tipos possíveis de mapa. Com esse conjunto em mãos, eles coloriram todos com quatro cores e o teorema estava provado.

É importante notar que tanto para encontrar os 1.936 mapas quanto para os colorir, Haken e Appel usaram os computadores disponíveis na época, tornando essa a primeira grande demonstração a ser realizada por exaustão através de um computador. Beleza matemática é algo relativo, mas dificilmente um matemático diria que enumerar 1.936 casos possíveis do teorema e provar um resultado para todos configura estética matemática.

Pouco a pouco a demonstração foi aceita, e hoje é tida como a demonstração padrão do problema das cores. Em uma esfera ou plano, apenas quatro são necessárias. Se, contudo, seu planeta fosse uma rosquinha, você precisaria de sete cores para preencher todos os mapas. O número de cores necessárias para colorir um mapa possui uma relação profunda com a geometria do objeto, e abre diversas questões ainda mais difíceis de responder que o teorema das quatro cores.

Meu chefe na usina nuclear não conseguiu usar apenas quatro cores. Em sua pressa de enumerar os departamentos, fez escolhas ruins e achou que precisaria de cinco, tentando provar triunfante que essa história de teorema era furada. Nada pude dizer, sorri, culpei as canetas e passei toda aquela tarde tentando entender as siglas de muito mais que 1936 encanamentos, turbinas, aquecedores e motores.