O problema da festa, mais uma pitada de budismo

---

Paul Lockhart, o autor de um dos artigos mais lidos deste blogue (O Lamento de um Matemático), certa vez escreveu o seguinte: quando era jovem, ficou encantado com um problema chamado “Amigos numa Festa”. Tente resolvê-lo por si mesmo antes de ver a resolução que sugiro mais abaixo; ele é de fato um problema encantador.

O Problema da Festa. Imagine uma festa da qual participam n ≥ 2 pessoas. Mostre que, nessa festa, existem pelo menos duas pessoas com exatamente o mesmo número de amigos que também estão na festa. Por exemplo, o indivíduo A é amigo de cinco pessoas que estão na festa, mas o indivíduo B também é amigo de cinco pessoas que estão na festa. (Não necessariamente A e B são amigos; não necessariamente eles são amigos das mesmas pessoas.) Portanto, mostre: Em qualquer festa na qual haja n ≥ 2 participantes, sempre existem pelo menos dois participantes com exatamente o mesmo número de amigos que também estão na festa.

*

*

*

*

*

Resolução. Não demora muito, e você terá a ideia de representar as pessoas com bolinhas, e de representar a relação simétrica “B é amigo de C” ao unir a bolinha B à bolinha C por meio de uma linha. Assim:

Essa é uma relação simétrica porque, se B é amigo de C, então C é amigo de B, isto é, B e C são amigos entre si. Pode começar com três bolinhas e desenhar todos os casos possíveis. (“Todos os casos” excluindo rotações, translações, e isomorfismos em geral.) O número ao lado de cada bolinha é igual ao número de amigos na festa.

Chame cada bolinha de “vértice”, cada traço a unir duas bolinhas de “aresta”, e o número ao lado de uma bolinha de “grau”. Isso é um grafo.

Se examinar desenhos desse tipo por tempo suficiente, perceberá que o número de amigos é igual ao número de arestas que partem de um vértice (ou que chegam a um vértice). Talvez você brinque com quatro vértices, cinco vértices, seis vértices, para ver se descobre um padrão. Talvez comece com os vértices soltos (sem nenhuma aresta), e tente ligá-los de modo a fazer com que cada um deles tenha um grau distinto de todos os outros.

E daí verá que isso não acontece de jeito nenhum. Por mais que insista, por mais que experimente, sempre há pelo menos dois vértices com o mesmo grau.

Depois de umas horas desenhando grafos com canetas coloridas, penso que finalmente terá a ideia de que não lida somente com um problema de existência, mas também com um problema de não existência:

O problema da festa: versão explicitando não existência. Mostre que, numa festa com n ≥ 2 participantes, jamais pode acontecer que cada participante na festa seja amigo de um número distinto de participantes da festa. Em outras palavras, se alguém perguntar a cada participante, “Quantos amigos você tem nesta festa?”, e se tomar nota das respostas num caderno, jamais acontecerá de anotar n números distintos entre si — pois sempre haverá pelo menos dois números iguais.

E quando estiver olhando um grafo completamente conectado (todos os vértices ligados a todos os outros), por exemplo um grafo completo com 6 vértices (acima), terá a seguinte ideia: com 6 vértices, o grau máximo de cada vértice é 5. Ora, se cada participante, comparado a todos os outros, é amigo de um número distinto de outros participantes da festa; e se cada participante pode ser amigo de no máximo cinco outros participantes; então você está lidando com a sequência de seis inteiros não negativos 0, 1, 2, 3, 4, 5. Porque, se você precisa de seis inteiros não negativos para atribuir um inteiro distinto a cada participante, mas o maior inteiro vale 5, então o menor inteiro tem de valer zero. Com isso, um dos participantes da festa não é amigo de ninguém mais naquela festa. Um dos vértices não está conectado a nenhum outro vértice. Faça o desenho.

E essa já é a solução! Se começa com um grafo completo de 6 vértices (por exemplo), o grau máximo é igual a 5, e para atribuir um inteiro distinto para cada vértice, precisa trabalhar com a sequência 0, 1, 2, 3, 4, 5 de inteiros não negativos. Contudo, ao apagar todas as arestas que chegam a um dos vértices, para obter um vértice com grau igual a zero, daí o grau máximo cai para 4 — fica impossível atribuir um inteiro não negativo distinto para cada um dos seis vértices.

Use aqui o princípio do pombal: se você tem seis pombos (seis vértices), mas só pode acomodá-los em cinco casas de pombos (os inteiros não negativos 0, 1, 2, 3, 4), então no mínimo dois pombos terão de ocupar a mesma casa — no mínimo dois vértices terão o mesmo grau; no mínimo dois participantes da festa terão o mesmo número de amigos também na festa.

Falta agora tornar essa solução perfeitamente geral. Suponha que tem diante de si n ≥ 2 vértices, e que, para cada vértice, você desenha n – 1 arestas ligando esse vértice a todos os outros. Agora tem diante de si um grafo completo com n vértices. Todos os vértices desse grafo têm grau igual a n – 1. Mas você deseja produzir um grafo no qual não haja dois vértices distintos com o mesmo grau, isto é, um grafo no qual não haja um par de vértices com o mesmo grau. Logo, terá de apagar algumas arestas aqui e ali.

Contudo, visto que tem n vértices, e que o maior grau possível é n – 1, para que não haja dois vértices distintos com o mesmo grau, terá de trabalhar com os n inteiros não negativos 0, 1, 2, 3, …, n – 1. E isso significa que o grau de um dos vértices vale zero.

Você escolhe um dos vértices e apaga todas as arestas que partem dele (ou que chegam até ele). Fazendo assim, os outros n – 1 vértices agora formam um grafo completo, cujos vértices têm todos o mesmo grau n – 2.

E isso significa que você não pode mais trabalhar com os n inteiros não negativos 0, 1, 2, 3, …, n – 1, pois tem de trabalhar com os n – 1 inteiros não negativos 0, 1, 2, 3, …, n – 2. Use o princípio do pombal: se tem diante de si n pombos (vértices), e se deve acomodá-los em no máximo n – 1 casas de pombos (inteiros não negativos), então terá de acomodar pelo menos dois pombos numa única casa de pombos — isto é, pelo menos dois vértices têm o mesmo grau.

Já pode escrever a resolução do problema da festa, mas sem mencionar vértices, arestas, e graus.

Suponha que n ≥ 2 pessoas estejam participando de uma festa, e que todas elas são amigas de todas as outras. Assim, cada participante dessa festa é amigo de outros n – 1 participantes dessa mesma festa. Mas você deseja saber se é possível haver uma festa na qual não haja dois participantes que são amigos do mesmo número de pessoas na festa, isto é, uma festa na qual não haja um par de participantes com o mesmo número de amigos também na festa. Logo, terá de “desfazer” algumas amizades aqui e ali.

Visto que tem n participantes na festa, e que cada participante é amigo de no máximo n – 1 pessoas que também estão na festa, ora, para que não haja dois participantes distintos com o mesmo número de amigos na festa, você terá de trabalhar com os n inteiros não negativos 0, 1, 2, 3, …, n – 1. E isso significa que um dos participantes não pode ser amigo de ninguém na festa. Ele é um completo desconhecido. Ele é um outsider. Ou talvez seja um penetra.

Você escolhe um dos participantes e “desfaz” todas as amizades que ele porventura tenha com outros participantes na festa. Fazendo assim, os outros n – 1 participantes podem ser amigos de, no máximo, outros n – 2 participantes da festa.

E isso significa que você não pode mais trabalhar com os n inteiros não negativos 0, 1, 2, 3, …, n – 1; em vez disso, tem de trabalhar com os n – 1 inteiros não negativos 0, 1, 2, 3, …, n – 2. Use o princípio do pombal: se tem diante de si n pombos (participantes da festa), e se deve acomodá-los em no máximo n – 1 casas de pombos (inteiros não negativos), então deve acomodar pelo menos dois pombos numa única casa de pombos — isto é, pelo menos dois participantes da festa são amigos do mesmo número de outros participantes que também estão na festa. ❏

*

Certa vez, disse o Buda a um de seus discípulos, “Não confie na mera lógica, ou em inferências, ou em aparências, ou em especulações.” O ponto essencial do budismo é olhar o mundo e vê-lo, mas vê-lo de um modo especial — é olhar o mundo atento ao fato de que a mente humana não se contenta em simplesmente ver o mundo: ela automaticamente separa tudo o que vê em objetos discretos (“isso está aqui”, “aquilo está ali”, “isso começou agora há pouco”, “aquilo terminou agora há pouco”), e cola rótulos abstratos ou emocionais em cada um deles (“bom”, “mau”, “inofensivo”, “perigoso”, “quero”, “não quero”, “gostaria que durasse para sempre”, “gostaria que acabasse logo”). Mal uma pessoa abre os olhos, diz o budista, e sua mente já cria uma realidade lotada de prejulgamentos, lotada de esperanças e medos, lotada de coisas as quais a mente gostaria de agarrar, ou de coisas as quais a mente gostaria de jogar longe. Essa realidade lotada de coisas discretas às quais estão colados rótulos abstratos ou emocionais é a fonte de uma quantidade imensa de sofrimento.

Não deveria ser assim, pois a Realidade não é assim. Até onde se pode ver, a Realidade sempre foi puro fluxo, pura fluidez. Começos e fins são sempre arbitrários; os limites entre isso aqui e aquilo ali são sempre arbitrários. A mente humana olha para a Realidade e vê puro fluxo, pura fluidez, como se fosse as águas de uma corredeira; mesmo assim, a mente adiciona a esse fluxo, a essa fluidez, um montão de rolhas: coisas discretas boiando corredeira abaixo. Diz o budista, “Olhe e veja: não há rolhas. Só há o fluxo, a fluidez da corredeira.”

É difícil explicar tais coisas com muitas palavras — e mais difícil ainda explicá-las com poucas. Nem vou tentar. O ponto é que o Buda disse, “Cuidado com lógica, cuidado com inferências.” Poderia ter dito, “Cuidado com matemática.”

A linguagem, em geral, e a matemática, em particular, tendem a reforçar a ideia de que existem coisas discretas. Afinal, com a ajuda da ponta de uma caneta, o leitor pode contar todos os símbolos que usei para escrever esta postagem — e obterá um número de coisas discretas. (Este parágrafo, por exemplo, contém 481 caracteres, incluindo espaços.) A certa altura deste texto, eu disse que a relação “A é amigo de B” é uma relação simétrica: se A é amigo de B, então B é amigo de A.

Isso existe na Realidade? Ou isso existe na realidade com “r” minúsculo, isto é, na realidade lotada de coisas discretas com rótulos abstratos e emocionais produzidos pela mente humana?

Olhe para todos os amigos que você conhece e veja. Usando uma escala de 0% a 100%, com 0% sendo “amigo da onça” e 100% sendo “o melhor amigo do mundo”, é fácil ver que, se A é 75% amigo de B, talvez B seja 38% amigo de A. Com uma relação de amizade perfeitamente simétrica, você resolveu o problema da festa, mas ao custo de ignorar a Realidade. Se um dia aplicar a resolução do problema a uma situação real, lembre-se da simplificação que foi obrigado a fazer na Realidade e do conselho do Buda, “Cuidado com a mera lógica, cuidado com inferências.”

Se o budista contemporâneo estiver certo, a Realidade é algo no qual não há começos e fins, não há limites entre isso e aquilo — há somente puro fluxo, pura fluidez. Mas a mente humana tende a ignorar a Realidade para, em lugar dela, postular uma realidade cheia de coisas discretas, que perduram no tempo inalteradas, cada uma das quais cheia de rótulos abstratos ou emocionais. E a prática da matemática tende a reforçar tal realidade derivada da Realidade, pois o praticante está sempre recorrendo a pressuposições simplificadoras, como a pressuposição necessária à resolução do problema da festa: a relação de amizade é simétrica. Como muitas vezes o praticante de matemática consegue usá-la para resolver problemas cotidianos complicados, fica feliz e nem percebe que não trabalhou com a Realidade ao resolver um problema, mas sim com uma realidade tipicamente humana. Como disse certa vez um budista famoso, Huang Po, “Rejeitamos a experiência real em troca de nossos pensamentos sobre a Realidade.” {FIM}

---

Observações:

1. Se gostaria de saber mais sobre budismo secular, posso recomendar dois livros muito bons: Buddhism Pure and Simple, de Steve Hagen; e Why Buddhism Is True, de Robert Wright. “Budismo secular” significa “budismo deste século” — é um budismo consistente com a matemática, a ciência, e a filosofia atuais. Assim, se a teoria dos jogos diz que, em certa situação, determinada decisão moral é prejudicial à sociedade; e se um budista famoso diz o contrário em algum dos textos sagrados do budismo; daí o budista secular aceita a teoria dos jogos e rejeita o texto sagrado. Visto que afirmações metafísicas não podem ser verificadas com os métodos da ciência, o budista secular é completamente agnóstico quanto a afirmações metafísicas.

2. Note que a prova do teorema subentendido no problema da festa é uma prova por contradição — você presume que é possível atribuir um inteiro não negativo distinto para cada um dos participantes da festa, e depois chega à conclusão de que tem de atribuir um mesmo inteiro a pelo menos dois participantes da festa, contradizendo assim a pressuposição inicial.

3. Você viu no texto: “Certa vez, disse o Buda a um de seus discípulos […].” Disse mesmo? Os textos extantes mais antigos do budismo foram escritos uns 400 anos depois da morte de Sidarta Gautama, o Buda. O budista secular sabe que existiu um sujeito que, anos depois, ficou conhecido como “o Buda”; sabe que esse sujeito provocou profunda impressão em seus contemporâneos; mas também sabe que não pode confiar 100% nos textos sagrados do budismo: eles são o resultado de séculos de tradição oral, na qual quem contou um conto talvez tenha acrescentado um ponto, e portanto devem ser encarados tão somente como ponto de partida.

4. Você pode adaptar o problema dos amigos numa festa para qualquer relação que seja simétrica: (a) Em qualquer festa com n ≥ 2 participantes, há sempre pelo menos dois participantes com o mesmo número de parentes que também estão na festa; (b) há sempre pelo menos dois participantes com o mesmo número de irmãos gêmeos que também estão na festa; (c) Em qualquer conjunto S com n ≥ 2 bolinhas marcadas cada uma delas com um único inteiro positivo, há sempre pelo menos duas bolinhas elementos de S marcadas com o mesmo inteiro (incluindo zero bolinhas marcadas com o mesmo inteiro); etc.

5. Esta é a última postagem de 2023. Desejo ao leitores em 2024 a capacidade de não perder uma oportunidade de praticar o bem.