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
como 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
\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 = [6,666...] = 6 
 15
5
\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 = 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
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 + 1 pombos. 
 
Demonstração: 
 
 Novamente por absurdo. Sempre teremos 
 
1 1m m
n n
\u2212 \u2212\u23a1 \u23a4 \u2264\u23a2 \u23a5\u23a3 \u23a6 
 
Se cada casa contiver, no máximo, 1m
n
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 pombos teremos, no máximo, n.
1m
n
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 
pombos. Mas, 
 
n. 1m
n
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 \u2264 n . 
1m
n
\u2212 = 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
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 + 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
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 + 1 = 
50 1
12
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 +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
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6 + 1= =
50 1
7
\u2212\u23a1 \u23a4\u23a2 \u23a5\u23a3 \u23a6+ 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