O princípio do pombal prova que algo existe sem o encontrar

Certeza aos 367, cara ou coroa aos 23

A distância entre o que é garantido e o que é provável é aqui enorme, e é o que torna surpreendente o problema do aniversário. Vinte e três pessoas dão já 50,7 por cento de probabilidade de duas partilharem data, e cinquenta e sete levam isso a 99 por cento — e no entanto a certeza continua a exigir 367, porque uma disposição em que todos os aniversários diferem continua possível até esse ponto. O princípio do pombal fala apenas da coluna garantida e cala-se sobre a outra. Recorrer a ele quando querias uma probabilidade produz um enunciado verdadeiro e inútil; recorrer à probabilidade quando era precisa uma garantia produz uma afirmação que falha justamente na disposição que não consideraste.

Provas de existência que escondem a resposta

Uma função de dispersão que transforma qualquer ficheiro num número fixo de bits tem mais entradas possíveis do que saídas, pelo que colisões têm de existir — dois ficheiros diferentes com o mesmo resumo — e o princípio do pombal prova-o numa linha. Encontrar uma é outra coisa por completo, e a segurança prática de um resumo assenta nessa distância: toda a gente sabe que as colisões lá estão, e para uma função sã ninguém produz nenhuma. A mesma figura aparece onde quer que haja um argumento de contagem: decide se algo é possível e deixa a busca intacta. É uma virtude quando precisas de saber que uma busca não é vã, e uma frustração quando esperavas uma morada.

Perguntas frequentes

Porquê 366 e não 365?

Porque o 29 de fevereiro é um aniversário possível e o princípio tem de sobreviver ao pior caso. Usar 365 gavetas daria uma garantia a 366 pessoas que falha assim que alguém do grupo nasceu num dia bissexto, e uma garantia que falha não é garantia. É essa a disciplina característica do princípio: cada contagem tem de ser o número de gavetas concebivelmente utilizáveis, não o habitualmente utilizado, e todo o raciocínio construído sobre o caso típico desaba precisamente no exemplo que alguém apresentará para o testar.

Há uma versão para gavetas desiguais?

Sim, e é o mesmo argumento de contagem escrito com mais cuidado. Se cada gaveta tem a sua própria capacidade, o que conta é a capacidade total: ultrapassa a soma e alguma gaveta está acima do seu limite, embora o princípio continue sem dizer qual. Há também um primo probabilístico, usado quando os objetos não são colocados por um adversário mas ao acaso, e dá limiares muito menores — o problema do aniversário é exatamente esse primo, e a distância entre 23 e 367 mede bem o que a hipótese de acaso te rende.