INSTITUTO DE APLICAÇÃO FERNANDO RODRIGUES DA SILVEIRA (UERJ)
MATEMÁTICA NO ENSINO MÉDIO – PROF. ILYDIO SÁ
MATEMÁTICA COMBINATÓRIA – PRINCÍPIO DAS GAVETAS (Dirichlet) ou
PRINCÍPIO DA CASA DOS POMBOS
Vamos imaginar a seguinte situação: que você tenha 4 pombos, para alojar em 3 casas
disponíveis. É claro que, obrigatoriamente, pelo menos dois desses pombos terão de
ficar em uma mesma casa.
Generalizando, podemos dizer que o princípio da casa dos pombos afirma que se n
pombos devem ser postos em m casas, e se n > m, então pelo menos uma casa irá conter
mais de um pombo. Outra versão, similar, tem o seguinte enunciado: “se dispomos de
(n +1) pombos para colocar em n casas, então, certamente que ao menos dois deles
terão de ser colocados em uma dessas casas.”
Matematicamente falando, isto quer dizer que se o número de elementos de um conjunto
finito A é maior do que o número de elementos de outro conjunto B, então uma função
de A em B não pode ser injetiva, ou seja, qualquer função de A em B terá que ter, pelo
menos, dois elementos com a mesma imagem.
É também conhecido como princípio das gavetas de Dirichlet, pois se supõe que o
primeiro relato deste princípio foi feito por Dirichlet1 em 1834, com o nome de
Schubfachprinzip ("princípio das gavetas").
O princípio da casa dos pombos é um exemplo de cálculo combinatório que pode ser
aplicado em muitos problemas formais, incluindo aqueles que envolvem um conjunto
infinito.
Embora se trate de um princípio simples ou mesmo elementar, esse princípio é bastante
útil para resolver problemas que, pelo menos à primeira vista, não são imediatos. Com
alguns exemplos, podemos estabelecer uma regra geral para a aplicação desse princípio.
Exemplo 1: Quantas pessoas, no mínimo, são necessárias para se ter certeza que haverá
pelo menos duas delas fazendo aniversário no mesmo mês?
Resposta: 13 pessoas. Pelo princípio da casa dos pombos, como são 12 os meses do
ano, se tivermos mais pessoas do que a quantidade de meses, obrigatoriamente, pelo
menos duas delas terão nascido no mesmo mês. Assim sendo, essa quantidade mínima é
13.
Exemplo 2: Você tem uma gaveta de meias, todas iguais, mas de cores variadas. 12
pares de meias brancas, 8 pares de meias pretas e 5 pares de meias azuis. Acontece que
ocorreu um problema com o fornecimento de energia elétrica e ficou tudo escuro. Você
precisa, para sair, pegar uma quantidade de meias que lhe garanta que duas ao menos
serão da mesma cor. Quantas meias você deve pegar no mínimo para ter essa certeza?”
1
Johann Peter Gustav Lejeune Dirichlet (Düren, 1805 — Göttingen, 1859) foi um matemático alemão, a
quem se atribui a moderna definição formal de função.
Resposta: 4 meias. Aqui, o que importa é apenas a quantidade de CORES existentes e,
como são meias de três cores distintas, pelo princípio da casa dos pombos,
precisaríamos pegar no mínimo 4 meias para que tivéssemos a certeza de que ao menos
duas seriam de mesma cor.
Exemplo 3: Quantas pessoas devem estar, no mínimo, em um grupo, para que
possamos garantir que ao menos 3 delas tenham nascido num mesmo dia da semana?
Resposta: 15 pessoas. Como a semana tem 7 dias, se tivéssemos 2 pessoas nascido em
cada dia da semana a coincidência solicitada ainda não teria sido alcançada. Com uma
pessoa a mais, pelo princípio da casa dos pombos, ao menos 3 delas teriam de ter
nascido no mesmo dia da semana, obrigatoriamente. Verifique que podemos formatar a
nossa solução do seguinte modo: 2 . 7 + 1 = 15 pessoas. (a semana tem 7 dias)
Exemplo 4: Quantas pessoas devem estar, no mínimo, em um grupo, para que
possamos garantir que ao menos 5 delas tenham nascido num mesmo mês.
Resposta: 49 pessoas. Observando o comentário do exemplo anterior, podemos
formatar a nossa solução de forma análoga, ou seja, 4 . 12 + 1 = 49 (o ano tem 12
meses).
Para você responder:
1) Quantos estudantes devem ter em uma turma para garantir que pelo menos dois
estudantes possuam a mesma nota no exame final, se a nota do exame varia de
a
? (As notas são dadas em números inteiros).
2) Qual o número mínimo de vezes que devemos jogar um dado comum (6 faces)
para que possamos garantir que um dos números será sorteado duas vezes?
3) Uma urna contém 7 bolas vermelhas, 4 bolas azuis, 5 brancas e 8 pretas.
Quantas bolas no mínimo devemos retirar (sem olhar) para que possamos
garantir a retirada de pelo menos três da mesma cor?