Aula 08 - Princípio da Casa dos Pombos
7 pág.

Aula 08 - Princípio da Casa dos Pombos


DisciplinaItn11 materiais40 seguidores
Pré-visualização2 páginas
1
 
 
 
Aula 8 
 
PRINCÍPIO DA CASA DOS POMBOS 
 
Objetivos 
 
Utilizar o Princípio da Casa dos Pombos para verificar a existência de solução de 
alguns problemas. 
Utilizar o Princípio da Casa dos Pombos para encontrar a solução de alguns 
problemas. 
 
 
Exemplo 1 
 
 Uma criança precisa pegar meias para acabar de se vestir para ir à escola. 
Como as janelas do quarto estão fechadas porque seu irmão ainda dorme, ela terá 
que pegá-las sem acender a luz. 
 Na gaveta há 26 meias misturadas: 10 meias pretas idênticas e 16 meias 
brancas idênticas. 
Qual a quantidade mínima de meias que a criança terá que retirar para 
garantir ter retirado um par de meias da mesma cor? 
 
 
 A primeira meia retirada é branca ou preta. A segunda pode ser da mesma cor da 
primeira ou não. Obviamente se retirou da mesma cor anterior já formou um par, mas não 
podemos garantir que isto ocorreu. Mas, com a retirada da 3ª meia, obrigatoriamente, 
terá retirado um par de meias da mesma cor. Logo, a quantidade mínima é 3. 
 
 Observando o esquema abaixo fica mais fácil entender o problema. 
 
 1ª retirada 2ª retirada 3ª retirada 
 
 branca (*) 
 branca 
 branca (*) 
 preta 
 preta (*) 
 
 
 branca (*) 
 branca 
 preta (*) 
 preta 
 
 preta (*) 
 
(*) significa obteve um par de meias da mesma cor. 
Fundação CECIERJ Maria de Fatima Soares da Silva
 2
 
 
 
Exemplo 2 
 
 Considerando um grupo com 13 pessoas, podemos afirmar que existem pelo 
menos 2 pessoas que aniversariam no mesmo mês? 
 
 Sim. Se o grupo fosse formado por até 12 pessoas, seria possível que elas 
fizessem aniversário em meses diferentes, ou seja, a primeira aniversariando em janeiro, 
a segunda em fevereiro, e assim por diante. Mas, havendo 13 pessoas, certamente, pelo 
menos duas delas comemoram o aniversário num mesmo mês. 
 
 Na realidade, em qualquer grupo com mais de 12 pessoas podemos garantir que 
existem pelo menos 2 pessoas que aniversariam num mesmo mês. É claro que 
poderemos ter todas as pessoas aniversariando num mesmo mês, assim como termos 
vários meses com mais de uma pessoa aniversariando, o que não contradizem a 
afirmação anterior. 
 
 
Nos exemplos anteriores usamos (mesmo sem ainda conhecermos) um resultado 
chamado Princípio da Casa dos Pombos ou Princípio das Gavetas de Dirichlet. Este 
resultado é utilizado em vários problemas quando desejamos verificar a existência ou não 
de elementos satisfazendo uma propriedade. A seguir, o seu enunciado e demonstração. 
Analise com cuidado a demonstração, pois ela facilita o seu entendimento. 
 
 
 
Princípio da Casa dos Pombos 
 
 Se n + 1 pombos são colocados em, no máximo, n gaiolas (ou casas) então, 
pelo menos, uma gaiola deverá conter, pelo menos, 2 pombos. 
 
Demonstração 
 
 Podemos demonstrar por absurdo da seguinte forma: se em cada gaiola for 
colocado, no máximo, um pombo, teremos colocado, no máximo, n pombos, o que é uma 
contradição pois temos n + 1 pombos. 
 
 
 
Princípio das Gavetas de Dirichlet 
 
 Se n + 1 objetos forem colocados em, no máximo, n gavetas então, pelo 
menos, uma delas conterá, pelo menos, dois objetos. 
 
 
 Observe que na formulação do Princípio da Casa dos Pombos usamos gaiolas (ou 
casas) e pombos e no Princípio das Gavetas de Dirichlet usamos gavetas e objetos. 
Numa linguagem não formal, se há mais pombos do que o número de casas então pelo 
menos uma casa será ocupada com 2 ou mais pombos. 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 3
 
 
 Voltemos ao exemplo 1. O que podemos considerar como pombos ou 
gaiolas? 
 
 As gaiolas são as cores branca e preta (n = 2) e os pombos são as meias. Pelo 
Princípio da Casa dos Pombos precisamos de n + 1 = 2 + 1 = 3 meias para garantirmos 
ter tirado um par de meias da mesma cor. 
 
 
 
Agora, analisemos o exemplo 2. O que podemos considerar como pombos 
ou gaiolas? 
 
 Neste caso, os meses do ano são as gaiolas (n = 12) e as pessoas são os pombos 
(n+1=13) que serão \u201cdistribuídos\u201d pelos meses do ano. 
 
 
 
Exemplo 3 
 
 Se as notas de uma prova valem de 1 a 10 (sem uso de casa decimal), 
quantos alunos uma turma deve ter para que, no mínimo, 2 alunos tirem a mesma 
nota? 
 
 Nesse caso, os pombos são os alunos e as casas, as notas. 
 
 Como temos 10 casas, precisamos de, no mínimo, 10 + 1 = 11 pombos. Logo, com 
11 ou mais alunos numa turma, poderemos garantir repetição de nota. 
 
 
 
Exemplo 4 
 
 Considere um quadrado com os lados medindo 3u.c. Na superfície 
quadrangular por ele determinada marque aleatoriamente 10 pontos. Mostre que 
pelo menos um dos segmentos determinados por esses pontos tem comprimento 
menor que ou igual a 2 u.c. (u.c. significa unidade de comprimento). 
 
 Vamos dividir o quadrado em 9 quadradinhos com os lados medindo 1u.c.. 
 
 
 
 Considerando os quadradinhos como casas e os pontos como pombos, a 
quantidade de casas (9) é menor que a de pombos (10). 
Fundação CECIERJ Maria de Fatima Soares da Silva
 4
 
 
Para qualquer marcação de 10 pontos na superfície inicial, pelo Princípio da Casa 
dos Pombos, pelo menos uma casa (quadradinho) terá pelo menos 2 pombos (pontos). 
 
Sabemos da Geometria Plana que a maior distância entre 2 pontos quaisquer num 
quadrado é a medida da diagonal. Num quadradinho de lado medindo 1u.c., a medida da 
diagonal é igual a 2 u.c.. 
 
 Logo, existirão, pelo menos, dois pontos cujo segmento por eles determinado mede 
no máximo 2 u.c.. 
 
 
 
 
 
 Podemos enunciar o Princípio da Casa dos Pombos de uma forma geral: 
 
 Se nk+1 pombos são colocados em n casas, então, pelo menos uma casa 
contém, pelo menos, k+1 pombos. 
 
Demonstração: 
 
 Novamente, vamos demonstrar por absurdo. Se cada casa contiver no máximo k 
pombos teremos colocado, no máximo, nk pombos, o que é uma contradição, pois temos 
nk+1 pombos. 
 
 
 
Exemplo 5 
 
 Uma prova de concurso possui 20 questões de múltipla escolha com quatro 
alternativas em cada, onde somente uma alternativa deverá ser marcada em cada 
questão. Qual o menor número de candidatos que este concurso deverá ter se 
quisermos garantir que pelo menos 3 candidatos terão marcado os seus cartões de 
resposta exatamente iguais? 
 
Cada questão tem 4 possibilidades de marcação. Como são 20 questões, pelo 
princípio multiplicativo há 43421
vezes20
4.....4.4 = 420 cartões de resposta diferentes. 
Consideremos cada cartão como uma casa e os candidatos