Princípio da gaiola dos pombos
O princípio da gaiola dos pombos, também conhecido como princípio das gavetas de Dirichlet, é um conceito matemático simples, mas muito poderoso. Ele diz o seguinte:
Se você tem mais pombos do que gaiolas e coloca cada pombo em uma gaiola, então pelo menos uma gaiola terá mais de um pombo.
Em termos formais, se você tentar colocar n + 1 objetos em n recipientes, pelo menos um recipiente conterá dois ou mais objetos.
Exemplo 1
(RACIOCÍNIO LÓGICO E ESTATÍSTICA_SEPLAG – 2010) Em uma caixa há 12 bolas de mesmo tamanho: 3 brancas, 4 vermelhas e 5 pretas. Uma pessoa, no escuro, deve retirar n bolas da caixa e ter a certeza de que, entre elas, existem três da mesma cor. Qual o valor de n?
Dados do problema:
- 3 bolas brancas
- 4 bolas vermelhas
- 5 bolas pretas
Na pior das hipóteses, para evitar formar um trio da mesma cor, quantas bolas podemos tirar?
- No máximo 2 brancas
- No máximo 2 vermelhas
- No máximo 2 pretas
Ou seja, podemos tirar 2 + 2 + 2 = 6 bolas e ainda não teremos 3 bolas da mesma cor, mas ao retirar a sétima bola, forçosamente teremos 3 bolas da mesma cor, pois só há 3 cores.
Exemplo 2
Uma empresa de desenvolvimento de sistemas é composta dos seguintes profissionais: 3 gerentes de projeto, 5 analistas de negócio e 7 especialistas em desenvolvimento web. Quantos profissionais, no mínimo, devemos escolher para termos certeza de que retiramos dois da mesma função?
Dados do problema:
- 3 gerentes de projetos
- 5 analista de negócio
- 7 especialistas em desenvolvimento web
Total de 3 funções diferentes.
Para evitar pegar dois da mesma função, podemos pegar no máximo 1 de cada função:
- 1 gerente de projeto
- 1 analista de negócio
- 1 especialista em desenvolvimento web
Isso dá um total de 3 profissionais, todos de funções diferentes.
Se escolhermos mais 1 profissional (totalizando 4), seremos forçados a pegar pelo menos dois da mesma função, pois só existem 3 funções diferentes.
Exemplo 3
Um grupo de 6 cozinheiros foi designado para fazer 50 pratos diferentes em um restaurante, mas cada prato deveria ser preparado por um único cozinheiro. No final do trabalho, todos os cozinheiros trabalharam e todos os pratos foram preparados. Portanto, é correto afirmar que:
a. um dos cozinheiros preparou 10 pratos.
b. cada cozinheiro preparou pelo menos 5 pratos.
c. um dos cozinheiros preparou apenas 2 pratos.
d. quatro cozinheiros prepararam 7 pratos, e o outros dois, 6 pratos.
e. pelo menos um dos cozinheiros preparou 9 pratos ou mais. ★
Nesse caso vamos associar os cozinheiros às gaiolas e os pratos aos pombos.
Temos 50 pombos (pratos) para distribuirmos em 6 gaiolas (cozinheiros), logo teremos 8 x 6 = 48, 8 pombos(pratos) por gaiola(cozinheiro) e ainda ficam 2 pombos de fora. Portanto, pelo menos um cozinheiro terá de preparar 9 ou mais pratos.