O Princípio da Casa dos Pombos

Neste artigo, vamos aprender e praticar, através de exercícios da FCC, o Princípio da Casa dos Pombos, que é um assunto bastante recorrente em provas de Raciocínio Lógico.

É importante frisar que esse assunto não aparece explícito nos editais, mas é cobrado dentro do chamado “Raciocínio Matemático“.

Uma das coisas que os matemáticos fazem é 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.

O Clássico Problema dos Aniversários

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, ou cem. Por quê?

Ora, porque embora com 100 pessoas em um auditório seja provável que existam 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.

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 podemos garantir 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.

Fios de Cabelo

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. Encontremos um argumento que convença quem perguntou algo que quer saber, e sem apelar para o recurso de zero cabelo.

Antes que eu escreva a resposta, uma possibilidade é imaginar que, se estou propondo esse problema nesse tópico, 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.

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. É 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? O censo de 2010 afirma que havia 1.537.704 pessoas. 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.

O Princípio das Gavetas

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.

Esse princípio é conhecido pelo nome de princípio da casa de pombos (ou princípio das gavetas, ou princípio de Dirichlet).

Se n+1 pombos forem distribuídos em n casas, então pelo menos uma delas conterá pelo menos 2 pombos.

Vamos resolver alguns exercícios recentes.

Questões FCC

01. (FCC 2019/Prefeitura de Manaus)

O número mínimo de pessoas em um grupo para que se garanta que, necessariamente, haja 7 delas que fazem aniversário no mesmo mês do ano é

a) 83.

b) 13.

c) 43.

d) 23.

e) 73.

Resolução

Imagine que você está em uma sala com muitas pessoas. Você vai sortear pessoas aleatoriamente até que sejam obtidas 7 pessoas que fazem aniversário no mesmo mês do ano.

Se você é uma pessoa sortuda, poderia sortear 7 pessoas consecutivas que nasceram no mês de setembro, por exemplo. Assim, contando com a sorte, precisaríamos de apenas 7 pessoas.

Mas isso não é garantia. Para resolver esse problema, precisamos do número mínimo de pessoas para garantir que pelo menos 7 fazem aniversário no mesmo mês.

Para ter essa garantia, devemos pensar na pior das hipóteses, ou seja, você precisa imaginar que é uma pessoa extremamente azarada.

Queremos pelo menos 7 pessoas que nasceram no mesmo mês. Qual é a pior das hipóteses nesse caso?

Sortear 6 pessoas que nasceram em janeiro, 6 pessoas que nasceram em fevereiro, 6 pessoas que nasceram em março, …, 6 pessoas que nasceram em dezembro.

Assim, com 12 * 6 = 72 pessoas, não podemos garantir que haverá pelo menos 7 nascendo no mesmo mês. É claro que é muito provável que isso não aconteça, mas, como queremos garantir, devemos pensar no pior cenário.

Pois bem, no pior cenário, sorteamos 72 pessoas e não pudemos garantir que havia algum mês com 7 aniversariantes, pois seria perfeitamente possível haver 6 aniversariantes em cada mês do ano.

Mas agora não temos como fugir: a 73ª pessoa sorteada será obrigada a coincidir com 6 aniversariantes de algum mês.

Não estou dizendo que com 73 pessoas teremos APENAS 7 pessoas que fazem aniversário no mesmo mês. Pode até ser que as 73 pessoas façam aniversário no mesmo dia, mas não podemos garantir isso!

O que estou dizendo é que, mesmo na pior das hipóteses, no cenário de sermos MUITO azarados, precisaríamos de 73 pessoas para garantir que pelo menos 7 fazem aniversário no mesmo mês.

A resposta é a alternativa E.

E o que isso tem a ver com casa de pombos? Ora, basta pensar que cada mês do ano é uma casa de pombo. Assim, queremos saber a quantidade mínima de pombos para garantir que, dentre 12 casas de pombos, haverá alguma casa com pelo menos 7 pombos.

Gabarito: E

02. (FCC 2019/Prefeitura de Manaus)

As peças de um jogo estão todas dentro de um saco opaco. Elas vêm em 4 formatos diferentes e cada peça está numerada com um número  dentre os seguintes: 1, 2, 3, 4 ou 5. A menor quantidade de peças que devem ser retiradas aleatoriamente do saco para garantir que se tenha, após a retirada, pelo menos 4 peças de um mesmo formato e 3 peças com a mesma numeração é

a) 15.

b) 10.

c) 24.

d) 18.

e) 13.

Resolução

A grande dica para resolver questões desse estilo é pensar em casos extremos. Em outras palavras, você deve pensar que é uma pessoa extremamente azarada.

O nosso objetivo é retirar no mínimo 4 peças de mesmo formato e 3 peças com a mesma numeração.

Vamos começar pensando sobre as 4 peças de mesmo formato. Para facilitar o entendimento, vamos supor que as peças são triangulares, quadradas, pentagonais ou circulares (4 formatos diferentes).

Queremos retirar pelo menos 4 peças de mesmo formato. Se tivéssemos muita sorte, poderíamos retirar prontamente 4 quadrados, por exemplo.

Mas as peças são retiradas aleatoriamente e queremos a menor quantidade de peças para garantir que pelo menos 4 peças de mesmo formato serão retiradas. Não devemos contar com a sorte. Devemos pensar na pior das hipóteses como se fôssemos as pessoas mais azaradas do mundo.

Qual a pior das hipóteses? Ora, se eu sou muito azarado e quero retirar 4 peças de mesmo formato, então a pior das hipóteses é retirar 3 peças de cada formato. Observe:

Assim, não podermos garantir que haverá 4 peças de mesmo formato ao retirar 4 * 3 = 12 peças. Isso porque, na pior das hipóteses, poderíamos ter 3 peças de cada formato. É claro que poderíamos ter mais de 3 peças de mesmo formato, mas não podemos garantir.

Mas agora não temos como fugir: a próxima peça retirada será obrigada a coincidir com 3 já retiradas. Assim, com 13 peças podemos garantir que, por mais azarada que a pessoa seja, haverá pelo menos 4 peças de mesmo formato. Pode até ser que existam mais de 4 peças de mesmo formato, mas na pior das hipóteses teremos pelo menos 4.

Vamos agora pensar na numeração. Queremos retirar 3 peças com a mesma numeração. Se fôssemos sortudos, poderíamos retirar (4, 4, 4) ou (1, 1, 1) logo de cara.

Lembre-se que devemos pensar na pior das hipóteses, pois queremos GARANTIR que dentre as peças retiradas haverá pelo menos 3 com a mesma numeração.

Qual a pior das hipóteses nesse caso? Retirar 2 peças de cada numeração.

(1, 1, 2, 2, 3, 3, 4, 4, 5, 5)

Observe que já retiramos 10 peças (2 de cada numeração) e não conseguimos as 3 peças de mesma numeração. Poderíamos ter conseguido se estivéssemos contando com a sorte. Mas é possível que uma pessoa seja tão azarada ao ponto de retirar 2 peças de cada numeração.

Logo, 10 peças não são suficientes para garantir que pelo menos 3 peças de cada numeração. Entretanto, a 11ª peça obrigatoriamente deverá coincidir com algum número já retirado e aí sim teremos pelo menos 3 peças de mesma numeração.

Em suma, temos:

– Precisamos de pelo menos 13 peças para garantir que haverá pelo menos 4 peças de mesmo formato.

– Precisamos de pelo menos 11 peças para garantir que haverá pelo menos 3 peças de mesma numeração.

Logo, 11 peças não são suficientes para atender as duas exigências, mas 13 peças sim. Com 13 peças podemos garantir as duas coisas: pelo menos 4 peças de mesmo formato e pelo menos 3 peças de mesma numeração.

Guilherme, o que isso tem a ver com o Princípio da Casa dos Pombos?

Vamos pensar nos formatos. São 4 formatos. Imagine que são 4 casas de pombos. Quantos pombos são necessários para garantir que haverá alguma casa com pelo menos 4 pombos? A pior das hipóteses seria colocar 3 pombos em cada casa. Assim, com 3 x 4 = 12 pombos não podemos garantir que haverá alguma casa com pelo menos 4 pombos. Mas, com a chegada do 13º pombo, teremos certeza que em alguma casa haverá pelo menos 4 pombos.

Gabarito: E

03. (FCC 2018/DETRAN-MA)

Os 25 caminhões da frota de uma empresa serão vistoriados no departamento de trânsito de uma cidade, para que recebam autorização especial para circular em determinada região do município. No dia da vistoria, cada veículo será encaminhado a um dos 10 fiscais do setor de fiscalização. Esse encaminhamento é feito por meio de um sorteio, realizado quando o caminhão é recepcionado no setor pelo próprio sistema de cadastro. Em relação ao resultado do sorteio, é correto afirmar que, necessariamente, 

a) pelo menos um fiscal vai vistoriar mais do que 2 caminhões da frota. 

b) cada fiscal vai vistoriar no mínimo 2 e, no máximo, 3 caminhões da frota. 

c) nenhum fiscal ficará livre de vistoriar caminhões da frota dessa empresa. 

d) nenhum fiscal vai vistoriar mais do que 3 caminhões da frota. 

e) os 25 caminhões não poderão ser vistoriados pelo mesmo fiscal.

Resolução

O que isso tem a ver com o Princípio da Casa dos Pombos? Vamos lá. Imagine que há 10 casas de pombos e devemos distribuir 25 pombos entre as casas. Ora, certamente alguma casa será obrigada a abrigar mais de 2 pombos. Por quê?

Imagine que somos muito azarados e os 10 primeiros pombos são distribuídos em casas diferentes.

Em seguida, vamos alocar mais 10 pombos: 1 em cada casa.

Assim, já temos 2 pombos em cada casa.

Ainda temos 5 pombos: obrigatoriamente eles deverão ocupar casas que já são ocupadas por 2 pombos. Portanto, em alguma casa haverá mais de 2 pombos.

No caso, temos que distribuir 25 caminhões entre 10 fiscais. Vamos analisar as alternativas.

a) pelo menos um fiscal vai vistoriar mais do que 2 caminhões da frota. 

Mesmo que fôssemos “azarados” e tentar espalhar os caminhões entre os fiscais de tal modo que cada um fiscalize poucos caminhões, seríamos obrigados a colocar pelo menos um fiscal com mais de caminhões. Isso porque a quantidade de caminhões é maior que o dobro da quantidade de fiscais.

Perceba a analogia com as casas de pombos que fiz. Essa alternativa é verdadeira.

b) cada fiscal vai vistoriar no mínimo 2 e, no máximo, 3 caminhões da frota. 

Nada impede que um só fiscal fiscalize todos os 25 caminhões (e os outros 9 fiscalizem nenhum). Portanto, a alternativa B está errada.

c) nenhum fiscal ficará livre de vistoriar caminhões da frota dessa empresa. 

Vimos que podemos, por exemplo, colocar todos os 25 caminhões para apenas um fiscal. Dessa forma, teríamos 9 fiscais que receberão nem um caminhão. A alternativa está errada.

d) nenhum fiscal vai vistoriar mais do que 3 caminhões da frota.

Falso. Já vimos que pelo menos um fiscal será obrigado a fiscalizar mais de 2 caminhões.

e) os 25 caminhões não poderão ser vistoriados pelo mesmo fiscal.

Falso. Vimos que é possível colocar os 25 caminhões para um único fiscal. Nenhuma informação do texto descarta essa possibilidade.

Gabarito: A

Ficamos por aqui. Espero que tenham gostado.

Forte abraço,

Guilherme Neves