Prof. Guilherme Neves

10/03/2016 | 01:52
Compartilhar

O princípio da casa dos pombos - FGV!!!

Oi, pessoal! 

Tudo bem?

Se em breve você fará o concurso do IBGE ou do MP/RJ, é um suicídio ir à prova sem saber o princípio da casa dos Pombos, também conhecido como Princípio das Gavetas, Princípio da Garantia Mínima ou Princípio de Dirichlet. Eu, particularmente, gosto de chamar de PRINCÍPIO DO AZARADO (este nome não é oficial...kkkk). Você vai entender porque gosto de chamar assim.

Este princípio não está explícito nos editais, mas entra na parte de PRINCÍPIOS DE CONTAGEM.

Uma das coisas que nós matemáticos fazemos é procurar padrões. Ou seja, procurar situações que se “repetem”. Assim, tentamos tirar algumas conclusões que permitam deduzir que, em face de certos antecedentes (caso se verifiquem hipóteses), produzem-se certos consequentes.

Vamos começar com exemplos bem simples.

Imagine que eu tenho 3 casas de pombos. Se eu possuo 4 pombos, então certamente em alguma casa haverá mais de um pombo. Se a quantidade de pombos é maior que a quantidade de casas, haverá certamente alguma casa com mais de um pombo. Foi pensando em exemplos como este que o princípio é chamado de Princípio da Casa dos Pombos.

Imagine agora que meu armário possui 5 gavetas. Se eu tenho 7 meias, certamente alguma gaveta conterá mais de uma meia, porque eu possuo mais meias do que gavetas. Foi pensando em exemplos como este que o princípio também é chamado de Princípio das Gavetas.

Imagine que eu tenho meias pretas, marrons, brancas e cinzas. Determinado dia faltou luz em minha casa e eu preciso retirar a quantidade mínima de meias para garantir que haverá PELO MENOS duas meias da mesma cor. Ora, vamos pensar na pior das hipóteses, ou seja, pense que você é a pessoa mais azarada do mundo.

Há 4 cores possíveis. Portanto, 4 meias não são suficientes, pois eu poderia retirar uma meia preta, uma marrom, uma branca e uma cinza. Mas, na quinta meia não tem como fugir: ela obrigatoriamente deverá repetir alguma das cores citadas. Assim, com 5 meias eu tenho certeza que terei PELO MENOS um par de meias da mesma cor. Pode até ser que eu tenha (por sorte) mais de duas meias da mesma cor, mas PELO MENOS duas eu garanto. Foi pensando na solução deste problema que eu comecei a chamar o princípio de PRINCÍPIO DO AZARADO (e é por isso que o princípio é chamado de Princípio da Garantia Mínima).

Na grande maioria dos problemas, você tem que imaginar que você é a pessoa mais azarada do mundo, tem que pensar na pior das hipóteses.

Vamos a mais um exemplo.

Em uma gaveta, há 4 meias pretas, 2 meias brancas, 8 meias cinzas. Qual é a quantidade mínima de meias que preciso retirar desta gaveta para garantir que terei pelo menos duas meias de cores diferentes?

Vamos pensar na pior das hipóteses? Ora, se eu estou querendo retirar duas meias de cores diferentes, o azar é pegar várias meias da mesma cor. Como eu sou MUITO AZARADO, eu começo a pegar meias cinzas (porque é a que tem maior quantidade). Sou tão azarado que pego 8 meias cinzas consecutivamente.

Depois que pego 8 meias cinzas, não tem como escapar. A próxima meia tem que ser de outra cor. Portanto, 9 meias é a quantidade mínima de meias para garantir que teremos pelo menos duas meias de cores distintas. Pode até ser que das 9 meias eu tenha mais de duas meias com cores diferentes, mas isso é sorte e não certeza.

Vamos agora analisar exemplos mais interessantes. Deixemos pombos e meias pra lá.

Quantas pessoas precisa haver em um auditório para ter certeza (eu disse CERTEZA!!!) de que pelo menos duas delas fazem aniversário no MESMO dia?

Não quero dizer que tenham nascido no mesmo ano, apenas que façam aniversário no mesmo dia.

Antes de escrever a resposta, quero pensar um momento junto com vocês (se é que já não responderam sozinhos). Vejamos: se houver duas pessoas, obviamente não há garantias de que as duas façam aniversário no mesmo dia. O mais provável é que não seja assim. Mas, além de provável (ou não provável), o fato é que estamos procurando CERTEZAS. E havendo duas pessoas no auditório nunca poderíamos ter certeza de que ambas nasceram no mesmo dia.

O mesmo aconteceria se houvesse três pessoas. Ou até dez. Ou cinquenta. Não? Ou cem. Ou duzentas. Ou até trezentas!!! Por quê? Ora, porque embora com trezentas pessoas em um auditório seja provável que haja duas que comemorem seus respectivos aniversários no mesmo dia, ainda não podemos assegurar ou garantir que o que queremos seja certo. É que poderíamos ter o AZAR de que todos tivessem nascido em dias diferentes do ano. Estamos nos aproximando de um ponto interessante na conversa...

Porque, se houvesse 365 pessoas no auditório, ainda não estaríamos em condições de assegurar que duas delas fazem aniversário no mesmo dia.  Poderia acontecer de todas terem nascido em todos os possíveis dias de um ano. Pior ainda: nem mesmo com 366 (por causa dos anos bissextos). Pode ser que justamente as 366 pessoas que há no auditório cubram exatamente todos os possíveis dias de um ano sem repetição.

No entanto, existe um argumento categórico: se houver 367 pessoas no auditório, não há como fugir: pelo menos duas têm de fazer aniversário no mesmo dia.

É claro que não sabemos quais são essas pessoas, nem se há mais de duas que atendem à propriedade pedida. Pode ser que haja mais... muito mais, mas isso não nos interessa. A garantia é que, com 367 pessoas, resolvemos o problema.

Agora, tendo em conta essa ideia que acabamos de discutir, vejamos outro problema: que argumento podemos encontrar para demonstrar a alguém que na cidade do Recife há pelo menos duas pessoas com o mesmo número de fios de cabelo na cabeça?

Claramente, a pergunta poderia ser respondida rapidamente apelando-se para os “carecas”. É certo que em Recife há duas pessoas que não têm cabelo e que, portanto, têm o mesmo número de fios de cabelo: zero!

Certo, mas evitemos esses casos.

Antes que eu escreva a resposta, uma possibilidade é imaginar que, se estou propondo esse problema nesse artigo, imediatamente após ter discutido o problema dos aniversários, é porque deve haver alguma relação entre os dois. Não é certo, mas é muito provável. E aí? Alguma ideia?

Uma pergunta, então: você tem ideia de quantos fios de cabelo uma pessoa pode ter na cabeça? Não que isso seja necessário para viver, mas dando uma pesquisada no Google, o resultado é que não há maneira de alguém ter mais de 200 mil fios de cabelo. Isso já seria o caso do King Kong ou algo assim. É impossível imaginar alguém com 200.000 fios de cabelo.

Com esse dado novo, de que serve saber que há no máximo 200 mil fios de cabelo na cabeça de uma pessoa? O que fazer com isso?

Quantas pessoas vivem no Recife? Entrei no site da Prefeitura e verifiquei que em 2000 a população recifense era de 1.422.905 habitantes. Para a solução do problema não é preciso ter o dado com tanta precisão. Basta dizer que há mais de 1 milhão de pessoas. Por que esses dados são suficientes?

Acho que a resposta está clara. Juntando os dois dados que temos (o da cota máxima de fios de cabelo que uma pessoa pode ter na cabeça e do número de habitantes da cidade), deduzimos que inexoravelmente o número de fios de cabelos entre as pessoas tem que se repetir. E não uma vez, mas muitas e muitas vezes.

Moral da história: usamos um mesmo princípio para tirar duas conclusões. Tanto no problema do aniversário como no dos fios de cabelo, há alguma coisa em comum: é como se tivéssemos um número de gavetas e um número de bolinhas. Se tivermos 366 gavetas e 367 bolinhas, e tivermos que distribuir todas, inexoravelmente deve haver pelo menos uma gaveta com duas bolinhas.

E se houver 200.000 gavetas e mais de 1 milhão de bolinhas para distribuir, reproduz-se o mesmo cenário: com certeza há gavetas com mais de uma bolinha.

Vamos resolver uma questão recente da FGV sobre este assunto?

(TJ-PI 2015/FGV) 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 6 estagiários trabalharão em 50 processos. Sabemos ainda que cada processo foi revisto por apenas um dos estagiários. Como todos os estagiários trabalharam, cada estagiário reviu pelo menos (no mínimo) um processo.

Vamos analisar cada uma das alternativas de per si.

(A) um dos estagiários reviu 10 processos;

Não podemos garantir. Seria possível ter 5 estagiários analisando 1 processo cada um e o sexto estagiário analisando 45 processos. Você pode imaginar muitas outras situações que tornam a alternativa A falsa.

(B) todos os estagiários reviram, cada um, pelo menos 5 processos;

Novamente não podemos garantir. Basta raciocinar da mesma maneira que a letra A. Se os cinco primeiros funcionários trabalharem com apenas um processo cada e o sexto funcionário com 45 processos, não podemos garantir que cada um dos estagiários reviu pelo menos 5 processos. 

Com o mesmo raciocínio percebemos que as alternativas C e D são falsas.

Vamos agora analisar a letra E, que é a resposta da questão.

(E) pelo menos um dos estagiários reviu 9 processos ou mais.

Vamos pensar na pior das hipóteses. Lembre-se que somos MUITO AZARADOS.

A alternativa E diz que temos certeza que PELO MENOS UM DOS ESTAGIÁRIOS REVIU 9 PROCESSOS OU MAIS.

Neste caso a pior das hipóteses é colocar cada estagiário para trabalhar com no máximo 8 processos. Ora, como são 6 estagiários, 6x8=48. Ainda sobram 2 processos. Assim, alguém terá que trabalhar com mais de 8 processos para completar o trabalho todos. Podemos, portanto, garantir que pelo menos um dos estagiários reviu mais de 8 processos (9 processos ou mais).

Espero que vocês tenham gostado. Um forte abraço, bons estudos e até a próxima.

Guilherme Neves


Comentários

  • 11/05/2016 - Carolina
    Professor,
    Muito bom! Tem outros artigos com exercicios comentados?
    Muito obrigada e Parabéns!
  • 11/05/2016 - Prof Guilherme Neves
    Oi, Carol!! Tenho muitos. Neste link https://www.pontodosconcursos.com.br/Artigo/137/guilherme-neves você pode encontrar todos os meus artigos. Obrigado!
  • 08/04/2016 - Érika
    Professor

    Quando você afirma " quantas pessoas precisa haver em um auditório pata ter certeza (eu disse CERTEZA) de que pelo menos duas delas fazem aniversário no MESMO dia?

    Existe a possibilidade de pensar que o mesmo dia seria do dia primeiro ao dia trinta e um, porque o mês tem 30 ou 31 dias? Neste caso, raciocinando assim, bastariam ter 32 pessoas no auditório?
  • 08/04/2016 - Prof Guilherme Neves
    Se você considerar "dia" apenas de 1 a 31, sim! A resposta seria 32.

    Se considerarmos dia como o dia do ano (dia/mês), então é como falei no texto.

    Abs!!

    Guilherme
  • 23/03/2016 - Sérgio Ferreira
    Muito bom!
  • 10/03/2016 - Pedro
    Muito bom o texto. Uma 1ª versão desse princípio: se m objetos são colocados em n gavetas ( n menor do que m) então "pelo menos" uma gaveta contém
    ((m - 1)/n) + 1 objetos. Na questão da FGV, teríamos m=50 e n=6. Fazendo o devido cálculo chegaríamos à resposta de que "pelo menos" um estagiário reviu 9 processos! Parabéns pelo artigo, Guilherme!
  • 10/03/2016 - Prof Guilherme Neves
    Olá, Pedro! Isso mesmo!! É impressionante a quantidade de aplicações deste princípio de enunciado tão simples, mas ao mesmo tempo tão poderoso. Fico feliz que tenha gostado. Abraço e bons estudos.
Comentar este artigo
MAIS ARTIGOS DO AUTOR
Compartilhar: