Princípio da casa dos pombos (PCP)

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 $\sqrt{2}$.

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 $a_1, a_2,..., a_{2010}$ e $b_1, b_2,..., b_{2010}$ duas permutações dos números 1,2,3,..,2010. Dizemos que elas se intersectam quando $a_k = b_k$ para algum valor de k com $1 \leq k \leq 2010$. 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 $x_1, x_2, x_3,..., x_{19}$ inteiros positivos menores ou iguais a 93. Sejam $y_1,y_2,..., y_{93}$ inteiros positivos menores ou iguais a 19. Prove que existe uma soma de alguns elementos $x_i$, diferente de 0, que é igual a soma de alguns inteiros $y_i$.

Referências

[1] Art of Problem Solving

[2] Po-Shen Loh - Pidgeonhole Principal