Aula 08 - Princípio da Casa dos Pombos

Prévia do material em texto

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 “distribuídos” 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 candidatoscomo pombos. Temos 
então n = 420. 
 
Se quisermos garantir que pelo menos 3 candidatos tenham marcado os seus 
cartões exatamente iguais, k +1 deverá ser igual a 3, de onde obtemos k = 2. 
 
Logo, 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 é nk + 1 = 420.2 + 1. 
 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 5
 
 
Denotemos por [A] o maior número inteiro menor que ou igual a A. 
 Exemplos: 20
3
⎡ ⎤⎢ ⎥⎣ ⎦ = [6,666...] = 6 
 15
5
⎡ ⎤⎢ ⎥⎣ ⎦ = 3 
 
 
 
Uma outra maneira de enunciarmos o Princípio da Casa dos Pombos é a seguinte: 
 
 Se m pombos são colocados em n casas, m > n, então pelo menos uma casa 
conterá, pelo menos, 1m
n
−⎡ ⎤⎢ ⎥⎣ ⎦ + 1 pombos. 
 
Demonstração: 
 
 Novamente por absurdo. Sempre teremos 
 
1 1m m
n n
− −⎡ ⎤ ≤⎢ ⎥⎣ ⎦ 
 
Se cada casa contiver, no máximo, 1m
n
−⎡ ⎤⎢ ⎥⎣ ⎦ pombos teremos, no máximo, n.
1m
n
−⎡ ⎤⎢ ⎥⎣ ⎦ 
pombos. Mas, 
 
n. 1m
n
−⎡ ⎤⎢ ⎥⎣ ⎦ ≤ n . 
1m
n
− = m -1 < m , o que é uma contradição. 
 
 
 
 
Exemplo 6 
 
 Numa rua existem 54 casas numeradas com números de 1 a 106. Mostre que 
existem pelo menos 2 casas com números consecutivos. 
 
Se a 1ª casa tiver o nº 1, a 2ª casa o nº 3, a 3ª casa o nº 5, e assim por diante, para 
evitar que duas delas tenham números consecutivos, a n-ésima casa teria o número 
1+2(n-1) com n variando de 1 a 53. Verifique! 
 
 A 54ª casa teria que ter o número [1 + 2.(54 - 1)] = 107 para não haver número 
consecutivo, mas a numeração vai até 106. Logo, alguma casa terá que ter número par 
existindo, portanto, pelo menos duas casas com números consecutivos. 
 
 Refaça o exemplo atribuindo à 1ª casa o número 2, à 2ª casa o número 4, e assim 
por diante e verifique que existem pelo menos 2 casas números consecutivos. 
 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 6
 
 
Exemplo 7 
 
Num grupo de 18 crianças há pelo menos um dia da semana em que pelo 
menos 3 nasceram. 
 
De fato. Como temos 7 dias na semana (n = 7) e m = 18, pelo Princípio da Casa 
dos Pombos, existirá, pelo menos, um dia na semana em que, pelo menos, 
18 1
7
−⎡ ⎤⎢ ⎥⎣ ⎦ + 1 = 2 + 1 = 3 
crianças nasceram. 
 
 
 
 
Observação 
Embora o princípio da Casa dos Pombos tenha um enunciado bem simples, ele 
pode ser usado para resolvermos problemas muito difíceis. Entretanto, esta não é a 
nossa proposta de trabalho. 
 
 
 
 
 Exercícios propostos 
 
1) Uma caixa contém 8 bolas azuis, 10 bolas brancas e 6 bolas verdes. Ao selecionarmos 
bolas uma a uma, aleatoriamente, qual a quantidade mínima de bolas que precisamos 
retirar para garantir que pelo menos 
a) 2 bolas escolhidas são da mesma cor? 
b) 4 das bolas escolhidas são da cor branca? 
 
2) Diga se cada uma das afirmativas abaixo é verdadeira ou falsa. Em qualquer caso, 
justifique corretamente. 
Num salão estão 50 pessoas. Posso afirmar que nesse salão existem pelo menos 
a)5 pessoas que aniversariam no mesmo mês. 
b)2 pessoas que nasceram no mesmo ano. 
c)6 pessoas que nasceram no mesmo dia da semana. 
d)2 pessoas que nasceram no mês de janeiro. 
 
3) Mostre que em um grupo de 61 pessoas, pelo menos 6 têm o mesmo signo. 
 
4) Uma lanchonete possui 20 mesas e 62 cadeiras. Distribuindo as cadeiras ao redor 
das mesas, sempre existirá, pelo menos uma mesa com pelo menos 4 cadeiras? 
 
5) Qual é o número mínimo de pessoas que deve haver num grupo para que possamos 
garantir que nele haja pelo menos 8 pessoas nascidas num mesmo mês? 
 
6) Uma caixa contém 100 bolas misturadas e de cores distintas. Destas, 30 são 
vermelhas, 30 são verdes, 30 são azuis e, entre as 10 restantes, algumas são brancas e 
outras são pretas. Qual o menor número de bolas que devemos tirar da caixa, sem 
 
Fundação CECIERJ Maria de Fatima Soares da Silva
 7
 
 
reposição e aleatoriamente, para termos certeza de haver retirado pelo menos 10 bolas 
da mesma cor? 
 
7) Dois funcionários de uma loja ao receberem 43 caixas de laranjas percebem que elas 
são de 4 espécies diferentes, mas que todas as laranjas que estão em qualquer uma das 
caixas são da mesma espécie. Pode um dos funcionários concluir que há no mínimo 11 
caixas de uma mesma espécie de laranjas? 
 
 
Respostas (Não olhe antes de tentar bastante). 
1-a)Sejam as cores, as gaiolas e as bolas, os pombos. Temos n = 3 gaiolas (as cores 
azul, branca e verde). Pelo princípio da Casa dos Pombos, a quantidade mínima de bolas 
que precisamos retirar para garantir que pelo menos 2 bolas escolhidas são da mesma 
cor é n + 1 = 3 + 1 = 4. 
 
b)Para garantirmos ter retirado pelo menos 4 bolas brancas, teremos que ter tirado 
8 + 6 + 4 = 18 bolas, isto é, uma quantidade que envolva todas as verdes, as azuis e 4 
brancas. 
 
2 a)Verdadeira. 
O ano tem 12 meses e podemos considerar cada mês como uma casa. Seja n = 12. 
Pelo princípio da casa dos pombos pelo menos um mês terá pelo menos 
1m
n
−⎡ ⎤⎢ ⎥⎣ ⎦ + 1 = 
50 1
12
−⎡ ⎤⎢ ⎥⎣ ⎦ +1 = 5 pessoas aniversariando. 
 
b) Falsa. 
Como 50 é um número relativamente pequeno, nada pode nos garantir que pelo 
menos 2 pessoas nasceram no mesmo ano, podendo cada um tendo nascido num ano 
diferente. 
Se no salão estivessem, por exemplo, 200 pessoas e levando em conta a idade 
máxima a que chegou um ser humano até hoje, a resposta seria verdadeira. 
Podemos pensar que temos 50 pessoas (pombos) para serem distribuídas num 
número não determinado de anos (casas), mas que este número pode ser maior do que 
50. 
 
c)Verdadeira. 
A semana tem 7 dias (domingo, segunda, ..., sábado) e podemos considerar cada um 
deles como uma casa. Seja n = 7. 
Pelo princípio da casa dos pombos, pelo menos num dia da semana teremos pelo 
menos 1m
n
−⎡ ⎤⎢ ⎥⎣ ⎦ + 1= =
50 1
7
−⎡ ⎤⎢ ⎥⎣ ⎦+ 1 = 8 pessoas nascido. O teorema não garante a 
existência de mais de 8 pessoas nascendo num mesmo dia da semana, mas para 
qualquer número de pessoas menor do que 8 a afirmativa é verdadeira. 
 
d) Falsa 
Pelo item (a) podemos garantir que existirá pelo menos um mês em que pelo menos 5 
pessoas nasceram, mas o princípio da casa dos pombos, não garante qual é o mês. 
Portanto, poderá ninguém ter nascido em janeiro. 
 
4) Sim; 5) 85; 6) 38; 7) Sim. 
Fundação CECIERJ Maria de Fatima Soares da Silva