casa dos pombos

PRINCÍPIO DA CASA DOS POMBOS

CONTEXTO

• 
• Também conhecido como teorema de Dirichlet ou princípio das gavetas, há a suposição de que o primeiro relato da utilização deste princípio tenha sido feito por Dirichlet em 1834, dai o nome.
• Seu princípio consiste na ideia que "Dados n+1 objetos dentro de n gavetas então, pelo menos, uma das gavetas contem mais de um objeto", (no caso, quando Dirichelet observou era os pombos);
• Esse método é muito simples e é muito utilizado em Análise Combinatótia, sendo umas das suas principais ferramentas;

Slide 3

• 
• matematicamente estamos falando que se um numero de elementos de um conjunto finito A é maior do que o numero de elementos de um outro conjunto B, então uma função de A em B não pode ser injetiva.
• DICA: Sempre tente identificar quem são os pombos e quem são as gavetas;
• exemplos de demonstração simples sobre esse principio

Slide 4

• Dadas 3 pessoas então duas são do mesmo sexo
• num grupo de 13 pessoas, pelo menos 2 delas nasceram no mesmo mes
• esses exemplos bem simples demonstra diretamente o principio, claramente existe métodos mais avançado que tbm utiliza-se esse principio como :
• Os 20 candidatos aprovados em um concurso do Tribunal de Justiça serão colocados em 10 gabinetes de desembargadores. Se cada gabinete receber pelo menos um dos candidatos aprovados e cada um deles só puder ser lotado em um único gabinete, pode-se afirmar que
• a) pelo menos um dos gabinetes receberá dois dos candidatos aprovados.
• b) nenhum gabinete receberá mais de dois candidatos aprovados.
• c) cada gabinete receberá dois candidatos aprovados.
• d) pelo menos um dos gabinetes receberá dois ou mais candidatos aprovados.
• e) haverá gabinetes que receberão, cada um, apenas um dos candidatos aprovados.
• Resolução
• Sabendo que cada gabinete receberá pelo menos um dos 20 candidatos, vamos analisar cada uma das opções:
• A hipótese de colocarmos apenas 1 candidato apenas em 9 gabinetes, e 11 candidatos no gabinete restante já descarta as opções A, B e C.
• Se os candidatos forem divididos igualmente entre os gabinetes, eliminamos a opção E.
• Pelo Princípio da Casa dos Pombos (ou Princípio das Gavetas), a pior hipótese possível seria colocar 2 candidatos em cada um dos 10 gabinetes. Assim, não é possível deixar algum gabinete sem dois ou mais candidatos.
• Resposta: D
• 

Slide 5

• sempre suponha na pior das hipóteses
• vamos ver mais uma questão retirada de um vestibular
• (TJ PI – FGV 2015) Um grupo de 6 estagiários foi designado para rever 50 processos e cada processo deveria ser revisto por apenas um dos estagiários. No final do trabalho, todos os estagiários trabalharam e todos os processos foram revistos. É correto afirmar que:
• a) um dos estagiários reviu 10 processos;
• b) todos os estagiários reviram, cada um, pelo menos 5 processos;
• c) um dos estagiários só reviu 2 processos;
• d) quatro estagiários reviram 7 processos e dois estagiários reviram 6 processos;
• e) pelo menos um dos estagiários reviu 9 processos ou mais.
• Resolução
• Sabemos que 50 processos foram revistos por 6 estagiários. Como a questão diz que todos trabalharam, podemos concluir que cada um deles reviu pelo menos 1 processo.
• O contra exemplo extremo onde temos 5 estagiários com apenas um processo e 1 estagiário com os 45 restantes já elimina as opções A, B, C e D.
• Podemos confirmar que a letra E é a opção correta através do princípio da casa dos pombos ou das gavetas.
• Como 6 x 8 = 48, na pior das hipóteses podemos distribuir 48 processos entre os 6 estagiários, de modo que cada um fique com 8, e ainda sobrarão 2 processos. Assim, alguém terá que trabalhar com 9 processos ou mais para completar o trabalho.
• Resposta: E
• 

Slide 6

• Vamos para a ultima resolvida:
• Exercício 1 - (Concurso: MP-RJ - Técnico do Ministério Público - Área Administrativa. Banca: FGV - 2019) Um saco contém bolas brancas, vermelhas, azuis e pretas, sendo 5 de cada cor. Antônio retirou no escuro certa quantidade de bolas e disse: “Entre as bolas que retirei, há três da mesma cor”.
• Para que a frase dita por Antônio seja obrigatoriamente verdadeira, o número mínimo de bolas que ele retirou do saco é:
• (A) 9;
• (B) 10;
• (C) 11;
• (D) 12;
• (E) 13.
• Solução:
• O saco contém:
• 5 brancas;
• 5 vermelhas;
• 5 azuis;
• 5 pretas.
• Para retirar 3 bolas da mesma cor, no pior cenário possível, será preciso tirar no mínimo: 2 brancas, 2 vermelhas, 2 azuis, 2 pretas.
• Após a 8ª retirada, neste pior cenário possível, qualquer bola que seja retirada resultará em 3 bolas de mesma cor.
• Sendo assim, ele precisa, no mínimo, retirar 9 bolas para garantir que tirou 3 de cores iguais.
• A Alternativa correta é a letra A.