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 27 – 1 subconjuntos não-vazios. Logo, como 27
– 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 A0, A1,...,
An – 1, onde Ai é 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 A0, se tem somente um conhecido
estará em A1 e assim por diante, até An – 1, caso ela
conheça todas as outras n – 1 pessoas. Mas se o subconjunto A0 possui
alguém, An – 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.