Erdős e o método probabilístico: provar que algo existe usando o acaso
Paul Erdős não tinha casa, não tinha emprego no sentido comum e quase não tinha posses. Passou a vida viajando entre universidades com uma mala, chegando à porta de algum colega com a frase "meu cérebro está aberto" e deixando para trás uma torrente de teoremas e problemas em aberto que os matemáticos ainda estão elaborando hoje. Entre tudo o que criou, uma ideia se destaca por mudar o próprio jeito de fazer demonstrações. Chama-se método probabilístico, e no seu centro há um movimento que soa quase como trapaça: provar que algo existe recusando-se a construí-lo.
A pergunta: quando a ordem é inevitável?
Comece por um enigma de aparência simples. Numa festa com seis pessoas, quaisquer duas são amigas ou desconhecidas. Acontece que, entre seis pessoas quaisquer, você sempre encontra três que são amigas entre si ou três que são desconhecidas entre si. A ordem se impõe sozinha. O ramo da matemática que estuda quando isso tem de acontecer é a teoria de Ramsey, e ela associa um número à pergunta.
O teorema de Ramsey garante que esses números existem, mas não diz o tamanho deles. O desdobramento natural é: quão grande um grupo pode ficar e ainda assim evitar qualquer aglomerado monocromático de tamanho k? Responder isso significa provar que existe uma coloração engenhosa desse tipo. E é exatamente aí que construir uma na mão se torna impossível na prática, porque o número de colorações possíveis é astronômico.
O movimento de Erdős: não construa, conte
A sacada de Erdős, em 1947, foi parar de tentar projetar uma boa coloração e simplesmente colorir de forma completamente aleatória, deixando a aritmética fazer o trabalho. O argumento é curto o bastante para ser acompanhado inteiro.
Colora cada ligação jogando uma moeda
Tome n pessoas e considere a rede completa em que cada par é unido por uma aresta. Colora cada aresta de forma independente e aleatória, de vermelho ou de azul, cada cor com probabilidade um meio. Nenhuma esperteza, nenhum projeto. Só uma moeda honesta para cada aresta.
Meça a chance de um grupo ser monocromático
Fixe um conjunto qualquer de k pessoas. Entre elas há C(k,2) arestas, ou seja, k(k-1)/2 ligações. Que todas essas arestas tenham a mesma cor é improvável: a probabilidade é 2 × (1/2)^C(k,2), já que há duas cores e cada um dos C(k,2) lançamentos precisa concordar. Chame esse número pequeno de p.
Some o número esperado de grupos ruins
Existem C(n,k) grupos diferentes de k pessoas com que se preocupar. Pela linearidade da esperança, o número esperado de grupos inteiramente monocromáticos é apenas a quantidade de grupos vezes a probabilidade de cada um: C(n,k) × 2 × (1/2)^C(k,2). Essa única expressão captura, em média, quantos aglomerados de uma só cor uma coloração aleatória vai conter.
Se a média fica abaixo de 1, uma coloração impecável tem de existir
Agora escolha n em torno de 2^(k/2). Com essa escolha, o número esperado acima fica menor que 1. Mas a contagem de grupos monocromáticos de verdade é um número inteiro e, se a média sobre todas as colorações fica abaixo de 1, então pelo menos uma coloração precisa marcar 0. Essa coloração não tem nenhum grupo monocromático de tamanho k. Portanto R(k,k) é maior que n, que é cerca de 2^(k/2).
Leia esse último passo de novo, porque nele está toda a mágica. Nunca produzimos uma boa coloração. Nunca descrevemos uma. Mostramos que a coloração média é tão perto de impecável que uma perfeita é obrigada a existir em algum ponto da pilha. A demonstração entrega certeza sobre um objeto específico sem apontar para objeto nenhum.
Por que isso foi revolucionário
Antes de Erdős, provar que algo existia quase sempre significava construir a coisa ou, no mínimo, descrever um procedimento que a construísse. O método probabilístico quebrou essa expectativa. Ele estabeleceu que o próprio acaso pode servir de demonstração: se uma tentativa aleatória tem sucesso com qualquer probabilidade acima de zero, então o sucesso é possível, ponto final.
Esse sabor não construtivo coloca o argumento na mesma família de alguns dos resultados mais elegantes da matemática. O argumento diagonal de Cantor também prova a existência de algo, um número ausente de qualquer lista, por pura força lógica em vez de construção explícita. Os dois compartilham aquele poder silencioso e um tanto perturbador: a conclusão é irrefutável ainda que nunca mostre a coisa que promete. O acaso usado aqui se apoia nas mesmas bases tratadas em entendendo probabilidade de forma intuitiva, onde a ideia de valor esperado, o motor do terceiro passo, é construída do zero.
Os problemas de Erdős e o momento da IA
Erdős não só provou teoremas. Ele propôs problemas, centenas deles, muitas vezes com pequenos prêmios em dinheiro que iam de alguns dólares por um exercício capcioso a milhares por uma questão que ele considerava realmente profunda. Muitos desses problemas continuam abertos, e foram cuidadosamente catalogados e mantidos em erdosproblems.com.
O zen de tudo isso
O método probabilístico é bonito pelo mesmo motivo que um bom truque de mágica é: você acompanha cada passo, não consegue achar o ponto em que foi enganado e ainda assim o resultado continua parecendo impossível. Não há prestidigitação. O valor esperado realmente fica abaixo de um, e um número inteiro abaixo da própria média realmente precisa cair a zero em algum lugar. A certeza é total, a construção é ausente, e as duas coisas são verdadeiras ao mesmo tempo.
Essa é a lição duradoura que Erdős deixou. Existência e construção não são a mesma coisa. Às vezes o jeito mais limpo de saber que existe um objeto perfeito por aí é provar que o objeto médio é quase perfeito e deixar a diferença fazer o resto. Para outro resultado em que uma única linha amarra ideias aparentemente sem relação, a identidade de Euler oferece o tipo oposto de beleza: onde Erdős faz a existência surgir da contagem, Euler crava um número exato e inevitável.
Perguntas frequentes
- O que é o método probabilístico?
- É uma forma de provar que existe um objeto com determinada propriedade sem construir o objeto diretamente. Você monta uma versão aleatória da coisa, mostra que a probabilidade de ela ter a propriedade desejada é maior que zero e conclui que pelo menos um objeto assim tem de existir. Paul Erdős foi o pioneiro da técnica, hoje uma ferramenta central em combinatória e em ciência da computação.
- O que Erdős provou com ele?
- Seu resultado marcante de 1947 deu um limite inferior para os números de Ramsey: ele mostrou que o número de Ramsey diagonal R(k,k) é maior que 2^(k/2). Em termos simples, existem maneiras de colorir as ligações de uma rede grande com duas cores de modo que nenhum grupo grande fique conectado inteiramente por uma única cor. Ele provou que essas colorações existem sem nunca exibir uma delas, apenas contando.
- Como é possível provar que algo existe sem construir?
- Usando médias. Se você escolhe um objeto ao acaso e calcula o número esperado de defeitos que ele tem, e esse número esperado fica abaixo de 1, então pelo menos um objeto do conjunto precisa ter zero defeitos. Um sorteio cuja média de defeitos é menor que um garante que existe um exemplar perfeito em algum lugar da coleção, mesmo que o argumento jamais aponte qual é.
- O que é um número de Ramsey?
- O número de Ramsey R(k,k) é o menor tamanho de grupo que força a ordem a aparecer, não importa como as coisas sejam arranjadas. Concretamente, R(k,k) é o menor número de pessoas tal que, seja qual for a forma de dividir cada par em amigos ou desconhecidos, você tem garantido um grupo de k pessoas que são todas amigas entre si ou todas desconhecidas entre si. O teorema de Ramsey diz que esses números existem; o método de Erdős mostra que eles crescem muito rápido.
- Por que o método probabilístico é importante hoje?
- Ele transformou o acaso numa técnica de demonstração, e essa ideia hoje atravessa a combinatória, o projeto de algoritmos, a teoria de códigos e a ciência da computação teórica. Muitos resultados sobre redes e algoritmos ainda são provados mostrando que uma construção aleatória funciona com probabilidade positiva. O método também explica por que boa parte dos próprios problemas de Erdős continua sendo alvo ativo de pesquisa.
Coloque em prática
Gostou de pensar sobre isso?
O Math Zen transforma esse tipo de intuição em prática diária, com exercícios adaptativos em 24 temas de matemática.
