quarta-feira, 1 de abril de 2009

O "Teorema" das 4 cores é falso!



O "Teorema" das 4 cores tem uma longa história. E também uma longa história de pseudo-demonstrações falhadas, quer por amadores quer por grandes matemáticos. Tim "Nerd" Ragnar parece ter dado uma machadada fatal naquilo que se julgava ser uma demonstração correcta - demonstração a que, curiosamente, os matemáticos mais "puros" sempre torceram o nariz por ser uma demonstração assistida por computador (na verdade, a primeira deste género) e ser impossível a um ser humano verificá-la.


O problema das quatro cores data de 1852, quando Francis Guthrie, na altura estudante de liceu, estava a colorir um mapa dos condados de Inglaterra. Guthrie constatou que, com algum esforço, conseguia colori-lo com a condição de condados contíguos terem cores diferentes usando apenas 4 cores diferentes. Intrigado, foi perguntar ao irmão mais velho, Frederick, já na Universidade, se isto se passava com qualquer mapa.

Frederick Guthrie não conseguiu responder, e foi perguntar ao seu eminente professor em Cambridge, o célebre Augustus de Morgan, se sabia resolver o problema. De Morgan pensou, pensou... e a resposta era não. Tinha nascido o problema das quatro cores.

Aqui começa a história das débâcles matemáticas, que agora tem pelos vistos um novo episódio. A primeira referência na literatura matemática à conjectura das quatro cores deve-se a Arthur Cayley em 1878. Um ano depois aparece a primeira "demonstração" pelo matemático Kempe; o seu erro foi apontado por Heawood 11 anos depois.

Outra demonstração errada deve-se a Tait, em 1880; o erro no raciocínio foi apontado por Petersen em 1891. Durante estes peiodos a conjectura das quatro cores foi considerada um "Teorema", e é provavelmente por isso que as empresas de lápis de cor (e hoje em dia de canetas para transparências) vendem pacotinhos de 4, e não 3 ou 5, canetas: julgava-se que 4 cores eram suficientes.

Seguiram-se contribuições matemáticas importantes de Birkhoff, que permitiram a Franklin mostrar em 1922 que a conjectura das 4 cores é verdadeira para mapas com, no máximo, 25 regiões.

Mais tarde Heesch introduziu técnicas importantes em teoria de grafos (redutibilidade e descarga) que permitiram a outros matemáticos reduzir a análise do problema a um número finito (embora gigantesco) de casos. Em 1976 os matemáticos Hapel e Akken conseguiram reduzir os casos possíveis a pouco mais de dois milhares e colocaram um computador a verificá-los um a um.

O resultado foi a primeira demonstração assistida por computador. O problema das quatro cores é, assim, um Teorema, embora nunca nenhum ser humano isolado tenha conseguido construir uma demonstração "clássica".

É neste contexto que surge o extraordinário contraexemplo de Ragnar! Não sendo um matemático profissional (e auto-intitulando-se "Nerd"), coloca a circular o contra-exemplo acima de um mapa plano que não se consegue colorir apenas com 4 cores.

A comunidade matemática está chocada. Mais uma demonstração para o lixo. Mas agora com a certeza de que o resultado é falso!

O que se passou mal com esta pseudo-demonstração? Aparentemente há uma subtileza em teoria de grafos que faz com que, tecnicamente, o grafo do mapa apresentado possua vértices imersivamente reduzidos e tal que o grafo dual (harmonicamente conjugado) não possui esta propriedade. Ainda não é claro, na altura da escrita, como é que este facto passou despercebido na "demonstração" por computador. Mas passou!

Aparentemente, o mapa de Ragnar é o menor com esta propriedade patológica, e portanto o mais pequeno contra-exemplo. O leitor é cordialmente convidado a tentar colorir o mapa com 4 cores. Atenção: a região exterior ("oceano") também deve ser colorida com uma das 4 cores.

14 comentários:

Roberto Dalmo disse...

Há um selo para o blog de vocês

http://quimicaeducacao.blogspot.com/2009/03/selo-vale-pena-acompanhar-esse-blog.html

abraços

nuvens de fumo disse...

Martin Gardner (1975)
LOLLLLLLLLLLLLLLLLLLL

Carlos Faria disse...

se o mapa tivesse colorido a mostrar a inconsistência da teoria dava mais jeito.

Ricardo Reis disse...

como seria possivel colorir o mapa para mostrar a dita inconsistencia? isso é q já se me afigura mais dificil...

Anónimo disse...

É possível colorir este mapa com 4 cores.

http://mathworld.wolfram.com/Four-ColorTheorem.html

John Aarson disse...
Este comentário foi removido pelo autor.
John Aarson disse...
Este comentário foi removido pelo autor.
Filipa M. disse...

Muito boa!

E o anagrama também!

John Aarson disse...

O anónimo tem razão. Este post é certamente uma mentira de 1 de abril! abraços.

Fernanda Carvalhal disse...

É mesmo uma mentira do 1 de Abril! Parabéns pela divulgação do Teorema das 4 cores.

Carlos Faria disse...

como se vê a inconsistência prova-se pela existência de uma solução que o permite colorir a 4 cores, só indicando que não existia tal possibilidade via informática e expondo os dados, seria aceitável o texto. excepto como peta ;)

rodrigo disse...

eu ja fiz esse teorema sera que nao tem mais difcil

matematico disse...

matematico ufrj.

não acreditem no que imbecil diz, está td errado...
o teorema é válido assim como o anagrama ...

fé na ciência !!!!!!!

Anónimo disse...

é possivel colorir esse mapa sim, inclusive eu ja consegui depois de quatro tentativas...
se duvidar entre en contato

gabrielalubk@hotmail.com

MORREU O NUNO

Homenagem possível a um poeta acabado de partir. Morreu o Nuno Júdice, coitado, prematuramente, o que é injusto. Com aquele seu ar desacti...