Prof. Evanilson Brandão

Princípio da Casa dos Pombos

O Principio da Casa dos Pombos nos diz que para colocarmos n + 1 pombos em n gaiolas, pelo menos uma gaiola deverá conter pelo menos dois pombos. Essa ideia tão óbvia é, na realidade, uma poderosa ferramenta na demonstração de muitos resultados bastante difíceis. O que, muitas vezes, torna o problema difícil é a construção de um conjunto ou conjuntos aos quais se possa aplicar esse princípio.

Esse princípio é também conhecido como “Princípio das Gavetas de Dirichlet” por ter sido por ele enunciado como: “Se n + 1 objetos são colocados em n gavetas, então pelo menos uma gaveta deverá conter, pelo menos, dois objetos”.

Exemplo 1. Mostrar que, numa festa de aniversário com mais de 12 crianças, existem pelo menos duas nascidas no mesmo mês e que também existem pelo menos duas nascidas no mesmo dia da semana.

Solução: Como temos mais crianças (pombos) do que meses (gaiolas), pelo menos um “mês” deverá conter pelo menos duas “crianças”. Na segunda parte, sendo o número de crianças maior do que 7, necessariamente duas ou mais terão nascido no mesmo dia da semana.

Exemplo 2. Mostrar que todo subconjunto de {1, 2, 3,..., 2n}, contendo n + 1 elementos, possui um par de elementos primos entre si.

Solução: É fácil observar que os únicos subconjuntos de {1, 2, 3,..., 2n} contendo n elementos, não-consecutivos, são{1, 3, 5,..., 2n – 1} e {2, 4, 6,..., 2n}. Portanto ao tomarmos um subconjunto com n + 1 elementos teremos, necessariamente, dois elementos consecutivos que, sendo primos entre si, irão garantir nosso resultado.  

Exemplo 3. Mostrar que qualquer subconjunto S de {1, 2, 3,..., 12} contendo sete elementos possui dois subconjuntos cuja soma dos elementos é a mesma.

Solução: Um subconjunto com 7 elementos terá soma no máximo igual a 6 + 7 + 8 + 9 + 10 + 11 + 12 = 63. Disto concluímos que os possíveis valores para a soma dos elementos de um subconjunto de um conjunto contendo 7 dos elementos de {1, 2, 3,..., 12} vão de 1 a 63, ou seja, temos 63 valores possíveis. Mas um conjunto com 7 elementos possui 2⁷ – 1 subconjuntos não-vazios. Logo, como 2⁷ – 1 > 63, pelo menos dois deles terão a mesma soma para os seus elementos.  

Exemplo 4. Mostrar que, dentre 9 pontos quaisquer de um cubo de aresta 2, existem pelo menos dois pontos que se encontram a uma distância menor  do que ou igual a Ö3 um do outro.

Solução: Dividimos este cubo em oito cubos menores dividindo cada aresta ao meio. Cada um dos 8 cubos assim gerados, tendo aresta 1, terá diâmetro igual a Ö3. Como temos 9 pontos, pelo menos um dos 8 cubos conterá 2 pontos, o que conclui a demonstração.

Exemplo 5. Suponhamos que os números de 1 até 15 sejam distribuídos de modo aleatório em torno de um círculo. Mostrar que a soma dos elementos de pelo menos um conjunto de 5 elementos consecutivos, tem que ser maior do que ou igual a 40.

Solução: Observe que, se somarmos todos os possíveis conjuntos de 5 elementos consecutivos (são 15), cada um dos números de 1 a 15 terá sido somado 5 vezes e que, portanto, a soma total será 5.(1 + 2 + 3 + ... + 15) = 5.(15 + 1).15/2 = 600. Como são 15 conjuntos distintos de 5 elementos consecutivos, se cada um tiver soma inferior a 40, o total será no máximo 15 ´ 39 = 585. Logo, pelo menos um deve ter soma maior do que ou igual a 40.

O Princípio da Casa dos Pombos pode ser, de maneira mais geral, enunciado como: “Se n gaiolas são ocupadas por n.k + 1 pombos, então pelo menos uma gaiola deverá conter pelo menos k + 1 pombos”.

Exemplo 6. Numa festa de aniversário com 37 crianças, pelo menos 4 nasceram no mesmo mês.

Solução: De fato, como 37 = 3.12 + 1 o resultado segue pelo caso geral enunciado acima, com n = 12 e k = 3. Logo temos que pelo menos 3 + 1 = 4 crianças nasceram no mesmo mês.

Exemplo 7. Se uma urna contém 4 bolas vermelhas, 7 bolas verdes, 9 bolas azuis e 6 bolas amarelas, qual é o menor número de bolas que devemos retirar (sem olhar) para que possamos ter certeza de termos tirado pelo menos 3 de uma mesma cor?

Solução: Consideramos como gaiolas as 4 cores diferentes e, portanto, tomando k = 2 e n = 4, temos 4.2 + 1 = 9 para a resposta do nosso problema.

Exemplo 8. Num grupo de n pessoas (n ³ 2) existem pelo menos duas pessoas com o mesmo número de conhecidos. (OBS.: Neste exemplo assumimos que a relação de conhecimento é simétrica, isto é, se a conhece b, então b conhece a.)

Solução: Vamos particionar estas n pessoas em subconjuntos A₀, A₁,..., A_{n – 1}, onde A_i é o subconjunto que contém as pessoas que conhecem i pessoas no grupo de n. Logo, se uma pessoa não conhece nenhuma outra das n – 1 pessoas ela estará no grupo A₀, se tem somente um conhecido estará em A₁ e assim por diante, até A_{n – 1}, caso ela conheça todas as outras n – 1 pessoas. Mas se o subconjunto A₀ possui alguém,  A_{n – 1} não possui ninguém e vice-versa. Isto porque se alguém não conhece ninguém é porque ninguém conhece todos e se alguém conhece todos os outros não ninguém que seja desconhecido de todos. Logo, as n pessoas estão particionadas em n – 1 subconjuntos e, portanto, algum subconjunto contém pelo menos duas pessoas, o que conclui a demonstração.

Introdução à Teoria dos Números, José Plínio de Oliveira Santos, IMPA/SBM.