Princípio da Casa dos Pombos

O enunciado é quase constrangedoramente simples, e as consequências são profundas. É um dos poucos resultados matemáticos que provam impossibilidade com um argumento de uma linha.

Enunciado

Se $n$ objetos são distribuídos em $m$ recipientes e $n > m$, então algum recipiente contém pelo menos dois objetos.

Equivalentemente: não existe função injetora de um conjunto finito num conjunto estritamente menor.

Forma generalizada. Se $n$ objetos vão para $m$ recipientes, algum recipiente contém pelo menos $\lceil n/m \rceil$ objetos.

Aplicações imediatas

Toda função de hash colide. Se o universo de chaves é maior que a tabela — e sempre é —, existem chaves distintas com o mesmo índice. Não há função de hash "perfeita" para entrada arbitrária, e toda tabela precisa de estratégia de resolução de colisão. Esse não é um defeito de implementação: é impossibilidade matemática.

Compressão sem perdas não comprime tudo. Um compressor sem perdas é uma função injetora de cadeias em cadeias. Se ele encurtasse toda entrada de $n$ bits, mapearia $2^n$ entradas em menos de $2^n$ saídas — impossível. Logo, para todo compressor existe entrada que ele aumenta. Compressores úteis apostam que as entradas reais são estruturadas, não que vencem a contagem.

Endereços IPv4 acabam. $2^{32}$ endereços para mais dispositivos que isso força compartilhamento — NAT é a resposta de engenharia a um argumento de contagem.

Detecção de ciclo. Uma função $f: S \to S$ sobre conjunto finito, iterada a partir de qualquer ponto, repete um valor em no máximo $|S|+1$ passos — e a partir daí entra em ciclo. É a base do algoritmo de Floyd (a "lebre e a tartaruga") e do algoritmo rho de Pollard para fatoração.

Geradores pseudoaleatórios têm período. O estado interno é finito, logo a sequência necessariamente se repete. O tamanho do estado limita o período: um gerador com 32 bits de estado não pode ter período maior que $2^{32}$.

Exemplos trabalhados

Meias na gaveta. Numa gaveta com meias pretas e brancas misturadas, quantas tirar no escuro para garantir um par igual? Três: com duas cores e três meias, alguma cor aparece duas vezes.

Aperto de mãos. Numa festa com $n \ge 2$ pessoas, sempre há duas que cumprimentaram o mesmo número de pessoas. Cada uma cumprimentou entre $0$ e $n-1$ pessoas — $n$ valores possíveis para $n$ pessoas, o que não bastaria. Mas $0$ e $n-1$ não podem ocorrer simultaneamente: se alguém cumprimentou todos, ninguém cumprimentou zero. Logo há no máximo $n-1$ valores efetivos para $n$ pessoas, e dois coincidem.

Subsequência monótona. Em qualquer sequência de $n^2+1$ números reais distintos existe subsequência monótona de comprimento $n+1$ — o teorema de Erdős-Szekeres, provado associando a cada elemento o par (maior subsequência crescente que termina nele, maior decrescente) e aplicando o princípio.

Soma divisível. Entre quaisquer $n$ inteiros, existe um subconjunto não vazio cuja soma é divisível por $n$. Considere as $n$ somas parciais $s_1, \dots, s_n$. Se alguma for divisível por $n$, pronto. Senão, seus restos estão em ${1,\dots,n-1}$ — $n$ valores em $n-1$ classes, então dois têm o mesmo resto, e a diferença entre eles é divisível por $n$.

O ataque do aniversário

A versão probabilística é ainda mais útil que a determinística. Com $m$ valores possíveis, a probabilidade de colisão passa de $50%$ após cerca de $1{,}18\sqrt{m}$ amostras — muito antes dos $m+1$ que o princípio determinístico exigiria.

Consequência prática em criptografia: uma função de resumo de $n$ bits oferece apenas $n/2$ bits de resistência a colisão. SHA-256 dá 128 bits de resistência a colisão, não 256. É por isso que resumos de 128 bits (como MD5) são considerados quebrados para essa finalidade.

Aplicações em computação

Cache. Um cache com $k$ posições atendendo mais de $k$ endereços distintos sofre evicção inevitável. O princípio dá o limite inferior para qualquer política de substituição.

Balanceamento de carga. Com $n$ requisições e $m$ servidores, algum servidor recebe pelo menos $\lceil n/m \rceil$. Nenhum balanceador escapa disso.

Alocação de registradores. Se o programa tem mais valores vivos simultaneamente do que registradores, algum precisa ir para memória. Isso conecta o princípio à coloração de grafos.

Estruturas de dados probabilísticas. Filtros de Bloom aceitam falsos positivos justamente porque o princípio proíbe representação exata em espaço sublinear.

Erros comuns

• Achar que o princípio localiza a colisão. Ele garante existência, não diz onde.
• Confundir a garantia determinística com a probabilística. Colisão garantida exige $m+1$ itens; colisão provável aparece por volta de $\sqrt{m}$.
• Esperar hashing sem colisão. Hashing perfeito só existe para um conjunto de chaves conhecido e fixo.
• Errar o teto na forma generalizada. É $\lceil n/m \rceil$, não $\lfloor n/m \rfloor$.

Leituras recomendadas

• Rosen, seção sobre o princípio da casa dos pombos — vários exercícios com aplicações em computação.
• Cormen et al., capítulo sobre tabelas hash — a análise de colisões que decorre diretamente do princípio.
• Katz e Lindell, capítulo sobre funções de resumo — o ataque do aniversário e suas consequências no dimensionamento de parâmetros.

Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill. ISBN 9781259676512. Jonathan Katz and Yehuda Lindell (2014). Introduction to Modern Cryptography. CRC Press. DOI: 10.1201/b17668.

Referências

1. Kenneth H. Rosen (2019). Discrete Mathematics and Its Applications. McGraw-Hill.
2. Jonathan Katz; Yehuda Lindell (2014). Introduction to Modern Cryptography. CRC Press.