As pontes de Konigsberg

Quando eu era garoto, conheci um problema de lógica e desenho que deve ser famoso. Apresentaram-me a seguinte figura:

Sendo o objetivo do problema desenhar essa figura sem tirar o lápis do papel e sem repetir os caminhos. Após algumas tentativas, cheguei a um caminho correto, desenhava feliz a casa com o X segundo as regras. Foi então que me foi apresentado uma variante do problema, “mais difícil” segundo aquele que me passou. Fui desafiado a desenhar essa outra figura:

Passei anos tentando, vez ou outra, resolver esse problema. Deixei de dar atenção a ele depois dos treze anos e, aos dezoito, descobri que todas aquelas tentativas fúteis de desenhar essa estranha flor foram justificadas: o problema não tem solução, é impossível encontrar um caminho que desenhe essa figura sem tirar o lápis do papel e sem repetir caminhos.

Mal sabia eu que esse mesmo problema, ou quase, havia sido resolvido por Leonhard Euler na cidade de Konigsberg, Prússia, em 1735. Euler garante com tranquilidade um lugar no top 3 da matemática, ostentando ainda hoje o título de matemático com maior número de publicações, tendo passado os dez últimos anos de sua vida cego (e publicando matemática, claro) e, segundo dizem, foi um excelente pai de seus cinco filhos. Ao passar pela cidade de Konigsberg na Prússia, Euler foi desafiado com um problema típico da cidade. Ela possuía duas ilhas no rio ligadas entre si e com a terra por sete pontes, como mostra a figura descaradamente roubada da Wikipédia:

E o desafio era atravessar as sete pontes sem repetir nenhuma. Você pode se divertir tentando, como os habitantes da cidade faziam, mas Euler decidiu pensar no problema de maneira mais profunda. A primeira coisa que fez foi se livrar do que estava sobrando: prédios, ilhas, estradas, apenas as pontes importavam:

Numerei as massas de terra para que a identificação com o desenho seguinte fique mais clara. Não contente, Euler percebeu que podia simplificar ainda mais o diagrama escrevendo-o da seguinte forma:

A vantagem desse formato, minimalista ao extremo, é nos permitir focarmos apenas no que realmente importa. E esse foi o raciocínio de Euler: quero atravessar todas essas linhas sem jamais repetir nenhuma. Rapidamente, ele notou que, para não repetir linhas, todo ponto a que ele chegasse deveria permitir uma saída, exceto, claro, pelos pontos inicial e final. Ou seja, para todo o ponto, exceto os de começo e fim, cada entrada deve possuir uma saída correspondente: ele deve possuir um número par de conexões. Se ele possui um número ímpar, digamos, 3; eu entrarei nele, sairei dele e, na próxima entrada, não terei como sair, eu travei e, ao menos que ele seja meu ponto final, perdi o jogo.

Olhe agora o diagrama das pontes de Konigsberg. Todos os pontos possuem um número ímpar de linhas, quando o número máximo é dois (entrada e saída). Assim, Euler concluiu de uma vez por todas que não é possível atravessar as sete pontes de Konigsberg sem jamais repetir nenhuma.

E Euler também responde a meu problema da flor estranha. Enquanto a casa com o X possui todos os vértices com um número par de linhas exceto pelos dois na “base” da casa, eu consigo criar o caminho e desenhá-la sem repetir linhas. E mais: sei sempre que os pontos de começo e fim serão os da base, é impossível fazer o caminho sem começar por eles, são os únicos com um número ímpar de conexões. Quanto à flor, todos os vértices do quadrado central possuem cinco conexões, qualquer caminho leva ao fracasso e meu problema está resolvido.

Curiosamente, quando trabalhava na usina nuclear, um colega propôs-me esse problema da flor, alegando que seria interessante já que eu “gostava dessas coisas” e que ele não conseguia resolver. Vingando-me daquele que em minha infância apresentou-me o problema, disse triunfante ser impossível e, naquela mesma lousa, contei as linhas de cada vértice. Porque matemáticos não levam muito bem a ideia de “não conseguirem algo” e, não conseguindo, ao menos provam que ninguém no mundo consegue.

Anúncios

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s