No coquetel de lançamento de uma startup em São Paulo, cada convidado recebeu um cartão de visita com um pequeno chip. Toda vez que duas pessoas se cumprimentavam, seus chips registravam o evento e somavam 1 ao contador pessoal de cada uma. Ao fim da noite, o CTO anuncia no telão: “Somamos todos os contadores e deu 8737”.
Um matemático comenta, imediatamente: “Xi, esse negócio está errado”. Só que ele estava meio bêbado e não disse o motivo.
- Havia exatamente 120 convidados.
- Cada aperto de mão entre duas pessoas soma 1 ao contador do chip de cada cartão.
O matemático está certo? Ou teria alucinado por efeito do coquetel?
Resposta:
Sim, o matemático está certo.
Como cada aperto de mão é contado duas vezes (uma para cada pessoa), o total de apertos de mão deve ser par.
Este é um caso particular do “Lema do aperto de mão” (handshake lemma), da Teoria dos Grafos. A lógica é exatamente a mesma, porém, a formulação é um pouco mais assustadora.
“O número de pessoas que apertam a mão um número ímpar de vezes deve ser par”.
Por exemplo, se eu apertei a mão de três pessoas, alguém deve ter apertado a mão de outros 1, 3, 5, 7, ou um número ímpar de vezes.
Este lema deriva da formulação do grande matemático Leonard Euler, para resolver o problema das 7 pontes de Konigsberg.
A cidade alemã de Konigsberg tinha 7 pontes. A população discutia se era possível atravessar todas as pontes, apenas uma vez, sem repetir nenhuma. Tente atravessar todas as pontes, uma vez apenas… e verá que é impossível. Por que?
Considere cada ponte uma aresta de um grafo e cada ilha um nó.
Se uma ilha (um nó) particular tem um número par de pontes, digamos duas, a pessoa consegue entrar e sair dela.
Se tem um número ímpar de pontes, ele só consegue entrar ou sair. A ilha deve ser o começo ou o fim da rota.
Do raciocínio acima, eu devo ter no máximo duas ilhas com número ímpar de pontes (uma para ser o início, outra para ser o final), e o resto dos nós deve ter um número par de pontes.
Porém, no caso das pontes de Konigsberg, tenho 4 ilhas com número ímpar de pontes, o que mostra que a resolução é impossível.
Euler era tão absurdamente genial que, para resolver um puzzle particular, criou todo um novo ramo de conhecimento, a Teoria dos Grafos!
Vide também:
https://www.scientificamerican.com/article/how-the-seven-bridges-of-koenigsberg-spawned-new-math/
O Compêndio de Ideias do Prof. Arnaldo: https://asgunzi.github.io/Compendium/
Forgotten Lore 