O Princípio de Pigeonhole é um dos principais conceitos por trás da análise combinatória. O princípio diz que:
Se x items são postos em y caixas, e x > y, então pelo menos uma caixa vai ter mais de 1 item.
Podemos entender melhor esse conceito analisando o diagrama abaixo:
Dessa forma, se tivermos mais pombos que caixas, teremos uma caixa para cada pombo (com sobra). Se tivermos o mesmo número de pombos e de caixas, ainda teremos uma caixa para cada pombo. Porém, se tivermos mais pombos que caixas, dois ou mais pombos terão de usar a mesma caixa.
Motivação
Este conceito pode até parecer sem aplicabilidade num primeiro momento, mas na verdade ele é fundamental em diversos assuntos. No caso da área de tecnologia, ele é fundamental para funções de hash.
Funções de Hash
Mais informações sobre a Funções de Hash
wikipedia.org
Hashing
Existem diversos algoritmos de hashing conhecidos, tais como o SHA-1, SHA-3, MD5, SHA-256, SHA-512 e entre tantos outros. Algoritmos estes usados para gerar hashes de arquivos, senhas ou textos, por exemplo.
Usando de exemplo o SHA-256, o número no nome do algoritmo representa a quantidade de bits no hash final, ou seja, 256 bits, resultando em 64 caracteres.
Entendendo mais sobre SHA-256
Mais informações sobre a Funções da família SHA-256
wikipedia.org
Sistema Hexadecimal
Mais informações sobre o Sistema Hexadecimal
wikipedia.org
O hash gerado por esse algoritmo é representado em hexadecimal, portanto o número total de possibilidades que o SHA-256 consegue criar, é o resultado de 16 símbolos em 64 posições diferente. Ou seja:
O SHA-256 é capaz de gerar 1.157920892373162e+77 combinações possíveis.
Este é um número finito, limitado. E como sabemos, podemos ter infinitos arquivos diferentes.
Dessa forma podemos estabelecer uma correlação:
∞ > 1.157920892373162e+77
Então, seguindo o Princípio de Pigeonhole, podemos ver que:
Os Hashes de arquivos ou senhas diferentes, podem acabar sendo iguais, independente de qual algoritmo esteja sendo usado.
Probabilidade
Como hashes são usadas em diversos sistemas diferentes, pode ocorrer essa duplicidade, o que não seria um problema justamente por se tratarem de sistemas diferentes (por exemplo, um sistema usado unicamente em uma empresa privada e um software usado apenas na China). Essa duplicidade seria um problema apenas no caso de hashes duplicadas em um mesmo sistema.
De toda forma, é algo pouco provável de acontecer, mas não impossível