ED 028

Quatro margens, sete pontes, um passeio

Sete pontes sobre o rio Pregel, cada uma cruzada uma vez só, e um passeio que os moradores tentaram fechar durante décadas.

Uma ponte de pedra sobre um rio escuro, vista de perto, com a margem oposta em sombra.

Uma das sete pontes sobre o Pregel

▼

Dá para atravessar todas as pontes de uma cidade passando uma vez só por cada uma? Dá, em muitas cidades, e a condição que decide o caso cabe numa contagem que você faz em trinta segundos sem sair da cadeira.

Essa contagem nasceu de um passatempo de domingo. Na cidade prussiana de Königsberg, cortada pelo rio Pregel, sete pontes ligavam as duas margens a dois pedaços de terra cercados pela água. Os moradores passeavam ali aos domingos e apostavam entre si um desafio simples de enunciar: sair de casa, cruzar as sete pontes, nenhuma delas duas vezes, e continuar andando até a última. Ninguém conseguia. Ninguém conseguia provar que era impossível também, e essa segunda parte é o que transforma um passatempo em problema de verdade.

Leonhard Euler recebeu o enunciado por carta em 1736 e, no começo, tratou o assunto com certo desdém. Escreveu a um correspondente que o caso lhe parecia trivial e sem relação com a matemática, porque a resposta dependia só de raciocínio e nenhum recurso da matemática conhecida ajudava a encontrá-la. Poucos meses depois ele mudou de opinião e apresentou à Academia de São Petersburgo um texto curto que resolvia o passeio e inaugurava um campo inteiro.

O que ele fez foi jogar fora quase tudo. A largura do rio não importa. O comprimento de cada ponte não importa. A distância que o caminhante percorre dentro de cada bairro não importa. Sobra um punhado de pedaços de terra e um punhado de ligações entre eles, e o problema inteiro passa a caber num desenho de rabisco.

Uma vez jogado fora o que não importa, aparece uma regra de contagem que não depende de tentar rota nenhuma. Ela olha para cada pedaço de terra, conta quantas pontes chegam ali e pergunta apenas se o número é par ou ímpar. Nada além.

Antes das pontes, fica de pé o rio com o bote de uma vaga, o lobo, a cabra e a couve esperando na margem de partida, e o barqueiro que precisa entregar as três cargas inteiras na outra margem.

Continue lendo ↓

I A resposta de ontem

Sete travessias e a volta que parece atraso

A rota que funciona começa pela cabra, e ela abre a única porta viável. Levar o lobo primeiro deixa cabra e couve sem vigia. Levar a couve primeiro deixa lobo e cabra sem vigia. Sobra uma porta só, e quem erra a primeira viagem já perdeu antes de remar.

A sequência completa tem sete travessias, contando cada retorno. Primeira: o barqueiro leva a cabra e a deixa na margem de chegada. Segunda: volta com o bote vazio. Terceira: leva a couve. Quarta, e aqui mora o enigma inteiro, volta trazendo a cabra de novo para a margem de partida. Quinta: leva o lobo, que fica em paz com a couve. Sexta: volta vazio. Sétima: leva a cabra pela segunda vez. Fim, três cargas inteiras.

A quarta viagem raramente aparece no papel de quem tenta. Ela desfaz metade do trabalho já entregue, e por isso a mão trava antes de traçá-la. Sem ela nenhuma rota fecha, e com ela todas as demais viagens saem óbvias.

Existe uma segunda rota válida, espelho da primeira: trocar a couve pelo lobo na terceira viagem e o lobo pela couve na quinta. Também dá sete travessias, e rota de cinco não existe.

Onde a solução realmente escapa

O erro mais comum não está na escolha da carga, e sim na conferência. Quem testa uma rota costuma olhar para a margem em que o bote acabou de encostar e esquecer da margem que ficou sem ninguém. O prejuízo acontece sempre nas costas do barqueiro, na margem que ele abandonou enquanto remava.

O segundo erro é procurar truque no enunciado. Amarrar a cabra numa árvore, fazer duas cargas caberem no bote, pedir ajuda a quem espera na margem de chegada. O enunciado não oferece material para nada disso.

Repare no formato da solução, porque ele reaparece hoje com outra roupa. O trabalho foi transformar um problema narrado em palavras numa lista curta de posições permitidas. Ninguém precisou de imaginação, precisou de representação.

O enigma de agora exige o mesmo movimento, e um pouco mais de coragem. Nas pontes não existe rota certa esperando ser achada. O trabalho é decidir, olhando só para o desenho, se existe alguma rota que fecha, e a decisão sai de uma contagem que cabe em quatro números.

II O Enigma do dia

Sete pontes sobre o Pregel e um único passeio

Königsberg tem quatro pedaços de terra: a margem norte, a margem sul, a ilha de Kneiphof no meio do rio e a língua de terra a leste, onde os dois braços do Pregel se juntam. Sete pontes ligam esses pedaços. Existe um passeio que cruze cada uma das sete pontes exatamente uma vez? Se existe, qual? Se não existe, por quê?

As ligações são estas, e vale desenhá-las antes de continuar. A ilha de Kneiphof recebe cinco pontes: duas vindas da margem norte, duas vindas da margem sul e uma que a liga à língua de terra a leste. A margem norte tem, além das duas que descem para a ilha, mais uma que a liga à língua de terra. A margem sul, do mesmo jeito, tem as duas da ilha e mais uma para a língua de terra. Somando sem contar duas vezes: sete pontes.

O passeio pode começar onde você quiser e terminar onde calhar. Não é exigido voltar à margem onde você começou. Não é proibido passar duas vezes pelo mesmo pedaço de terra, desde que a ponte usada seja outra. O que é proibido é repetir uma ponte, e é proibido atravessar o rio a nado ou de barco.

Onde quase todo mundo trava

O primeiro erro é atacar por tentativa. A vontade natural é rabiscar rotas até uma delas dar certo, e o número de sequências possíveis passa de cinco mil. Quem percorre todas termina sem saber se falhou por azar ou por impossibilidade.

O segundo erro é confundir o mapa com o problema. A planta de Königsberg tem ruas, prédios, o castelo, a catedral na ilha, e nada disso participa. Enquanto o desenho na sua folha tiver forma de cidade, a solução segue escondida atrás de detalhe inútil.

O terceiro erro é o mais interessante, e é ele que separa quem fecha o assunto de quem fica rabiscando. É acreditar que a resposta precisa ser uma rota. Uma prova de impossibilidade também é resposta, e costuma ser mais curta e mais definitiva que qualquer rota.

Cada pedaço de terra que não seja o começo nem o fim do passeio funciona como corredor: você entra por uma ponte e sai por outra. Toda visita gasta pontes aos pares. Um pedaço de terra com número ímpar de pontes só cabe no passeio como ponto inicial ou final.

Pense no que essa observação impõe. Um passeio tem um começo e um fim, ou seja, no máximo dois pedaços de terra podem se dar ao luxo de ter número ímpar de pontes. Agora conte as pontes de cada um dos quatro pedaços de Königsberg e veja quantos deles caem no ímpar.

A pergunta pede as duas partes. Escreva o número de pontes de cada um dos quatro pedaços de terra e diga quantos deles são ímpares. Depois responda se existe passeio, e sustente a resposta com a contagem, não com a quantidade de tentativas que falharam na sua folha.

Quem banca a edição de hoje

Patrocinadores mantêm a edição gratuita

III Sequência

Contar pontes em cada margem antes de andar

O material é uma folha, uma caneta e cinco minutos. Faça quatro bolinhas na folha: norte, sul, ilha e leste. Ligue as bolinhas com traços, um traço por ponte, sem se importar com o formato dos traços nem com a posição das bolinhas. Traços cruzados não atrapalham, traços tortos não atrapalham. O desenho não é um mapa, é um esqueleto de ligações.

O esqueleto faz metade do serviço porque expõe o único dado que decide o caso. Com as bolinhas na folha, o número de traços que sai de cada uma fica visível de relance, e é esse número que Euler chamou de grau do ponto em 1736, no texto que apresentou à Academia de São Petersburgo com o título Solutio problematis ad geometriam situs pertinentis.

1. Escreva ao lado de cada bolinha quantos traços saem dela. Confira somando os quatro números: o total tem que dar catorze, porque cada ponte é contada nas duas pontas. Se a sua soma não deu catorze, algum traço ficou faltando ou sobrando no desenho.

2. Marque com um círculo toda bolinha cujo número é ímpar. Ignore as pares por completo, elas nunca criam obstáculo. As ímpares são as candidatas obrigatórias a ponto de partida ou de chegada, e não existe terceiro lugar para elas.

3. Compare a quantidade de circuladas com dois. Zero circuladas: o passeio existe e volta ao lugar onde começou. Duas circuladas: o passeio existe e começa numa delas e termina na outra. Três ou mais circuladas: nenhum passeio existe, e o assunto está encerrado sem tentar rota nenhuma.

"Este problema, cuja solução ouvi ser tida como muito conhecida, é o seguinte: em Königsberg, na Prússia, há uma ilha chamada Kneiphof, e o rio que a cerca divide-se em dois braços, sobre os quais estão sete pontes."

Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, 1736.

Repare no que a abertura de Euler admite. O caso circulava como brincadeira conhecida, e ele não inventou o desafio, inventou o modo de olhar para ele. Foi preciso fabricar a ferramenta que faltava, e ela virou o começo da teoria dos grafos.

O método vale muito além do Pregel. Qualquer rede de traços e pontos passa pelo mesmo teste: percurso de carteiro, roteiro de catraca em museu, a casinha que criança desenha sem tirar o lápis do papel.

A Sequência é o placar de quem fecha sozinho. Um ponto por enigma resolvido antes de a solução aparecer, e o placar zera no dia em que você espia fora da hora. Um placar sem plateia ninguém falsifica.

Uma rota certa prova que o passeio existe, e nada mais. Uma contagem de paridade decide os dois casos de uma tacada: quando o passeio existe, ela diz por onde começar; quando não existe, ela encerra o assunto em quatro números.

"Quantas horas você já gastou tentando fazer algo que uma contagem de trinta segundos teria descartado?"

Teste hoje, em cinco minutos: desenhe a casinha clássica de traço contínuo, aquela do quadrado com telhado e um X no meio, e conte os traços que saem de cada vértice antes de encostar o lápis. Você vai achar exatamente dois vértices ímpares, os dois cantos de baixo. Comece por um deles e o desenho fecha na primeira tentativa. Comece por qualquer outro e falha sempre, sem exceção.