Por mais que o nome seja um pouco peculiar, a ideia inicial é simples e intuitiva (o que não a impede de resolver problemas complexos):
“Se temos a casas e b pombos, com a<b, há pelo menos uma casa com mais de um pombo”
Prova: Primeiramente, não queremos destruir nenhuma casa e muito menos cortar algum pombo, ou seja, nesse caso a e b são inteiros positivos. Vamos escrever b como sendo a+c , com c positivo, já que a<b. Desse modo, colocamos cada um desses a primeiros pombos em casas diferentes, ficando então com todas as casas ocupadas. Como não queremos deixar os outros c pombos desabrigados, eles terão que ir para casas já ocupadas, ou seja, pelo menos uma casa terá mais de um pombo.
Observação: Assim como os c pombos remanescentes podem se abrigar numa mesma casa já ocupada, eles podem se dividir e ir para casa diferentes, porém só o que podemos afirmar inicialmente é que no mínimo uma casa terá mais que um pombo.
Agora que já conhecemos esse teorema, vamos ver algumas de suas aplicações.
Exemplo 1: Qual o mínimo de alunos necessários numa sala de aula para garantir que os nomes de pelo menos dois deles tenham a mesma inicial?
Solução: Quando queremos garantir que algo acontece, temos que contar com o azar. É possível que o nome de um deles comece com A, o outro com B e assim por diante até acabarem as letras do alfabeto. Porém, o nosso alfabeto tem um número limitado de letras (26), ou seja, após os 26 primeiros alunos teríamos que repetir alguma letra. Desse modo a quantidade mínima é de 27 alunos.
No último problema, os alunos são os "pombos" e as letras do alfabeto são as "casas": quando já tínhamos usado todas as letras elas tiverem que ser repetidas.
Exemplo 2: Quantos alunos temos que ter numa escola para garantir que dois nasceram no mesmo mês?
Solução: Seja x esse mínimo de alunos e lembremos que um ano tem 12 meses. Sempre pensando num pior caso, supondo que todos nasçam num mês diferente. Essa situação acontece no mínimo até x < 13, pois quando x = 13, temos mais alunos do que meses e assim dois deles nascem no primeiro mês. Ou seja, o mínimo possível é 13.
Note que na última solução, escrevemos de maneira mais direta que quando o X número de "pombos"(alunos) é maior que o número Y de "casas"(meses), existe mais de um pombo por casa, ou, nesse problema, mais de um aluno por mês.
Exemplo 3: Se temos n números consecutivos, prove que pelo menos um deles é múltiplo de n.
Solução: Vamos supor que os números sejam x+1, x+2, ... , x+n. Existem n restos possíveis módulo n, que são {0,1,2,3...n-2,n-1}. Supondo que nenhum dos números seja divisível por n, o resto 0 não aparece, ou seja, temos n números e n-1 restos, o que nos diz que pelo menos um resto aparece duas vezes.
Considere que x+i e x+j tem o mesmo resto módulo n, ou seja n| x+i - (x+j), o que implica que n| i-j e, como i - j< n e i é diferente de j, isso não é possível.
Desse modo chegamos em um absurdo, o que faz com que nossa suposição inicial de que nenhum dos n números é múltiplo de n seja falsa, ou seja, um deles é múltiplo de n.
Problemas iniciais
Problema 1: Qual é a maior quantidade de números que pode ser selecionada dentre os números de 1 a 80 de tal modo que nenhum par tenha diferença igual a 8?
Problema 2: Em cada casa de um tabuleiro 3×3 é colocado um dos números −1, 0, 1. Prove que, dentre as oito somas ao longo de uma mesma linha, coluna ou diagonal, existem duas iguais.
Problema 3: Seja A={1,2,3,...,10} e B um subconjunto de A tal que |B|=6 (B tem 6 elementos). Prove que existem dois números em B cujo soma é divisível por 11.
Problema 4: Em um quadrado de lado 2, são escolhidos 5 pontos. Mostre que dentre os segmentos que unem dois desses pontos, pelo menos um dele tem tamanho menor ou igual a .
Problema 5: Considerando um grupo qualquer de n pessoas, prove que pelo menos 2 delas tem o mesmo número de amigos dentro do grupo.
Problema 6: 168 números de três dígitos são selecionados. Prove que é possível encontrar 8 deles tal que a soma de seus algarismos é igual.
Mais e mais problemas
Problema 7: Seja n um inteiro positivo e A={1,2,...,2n}. Se S é um subconjunto de A e tem n+1 elementos, mostre que existem dois elementos em S tal que um divida o outro.
Problema 8 (USAMO 1976): Cada quadradinho de um tabuleiro 4x7 é colorido de preto ou branco. Prove que, para qualquer coloração possível, o tabuleiro contém subretângulos de forma que os quadradinhos que estão em suas quinas tem a mesma cor.
Problema 9: Sejam e duas permutações dos números 1,2,3,..,2010. Dizemos que elas se intersectam quando para algum valor de k com . Mostre que existem 1006 permutações dos números 1,2,3,...,2010 tal que qualquer outra permutação com certeza tem uma intersecção com pelo menos um dessas 1006 permutações.
Problemas mais desafiadores
Problema 10: São dados 7 pontos dentro de um hexágono de lado 1, prove que existe um par de pontos entre esses tal que a distância entre eles seja no máximo 1.
Problema 11: Seja S um conjunto de 10 elementos positivos inteiros cujo soma total é menor que 250. Prove que existem A e B subconjuntos de S não vazios e de mesmo tamanho, tal que a soma dos elementos de A é igual a soma dos elementos de B.
Problema 12 (Putnam 1993): Sejam inteiros positivos menores ou iguais a 93. Sejam inteiros positivos menores ou iguais a 19. Prove que existe uma soma de alguns elementos , diferente de 0, que é igual a soma de alguns inteiros .
Referências
[1] Art of Problem Solving
[2] Po-Shen Loh - Pidgeonhole Principal