Princípio da Casa dos Pombos

Princípio da Casa dos Pombos

(Artigo organizado por Marcos Antônio Colins, professor de Matemática da Rede Estadual de Ensino do Maranhão)

O princípio da casa dos pombos também conhecido em alguns países (na Rússia, por exemplo) como Princípio de Dirichlet, pois foi o matemático Lejeune Dirichlet o primeiro a usar este método para resolver problemas não triviais. Outros matemáticos que se destacaram por usarem essa ideia para resolver diversos problemas foram os húngaros Erdös e Szekeres. Vamos abordar este princípio da seguinte maneira:

“Se em n caixas são postos n + 1 pombos, então pelo menos uma caixa terá mais de um pombo.”

Alguns Exemplos:

i. Em um grupo de três pessoas, pelo menos duas delas são do mesmo sexo;

ii. Em um grupo de 13 pessoas, pelo menos duas delas têm o mesmo signo;

iii. Em um grupo de 5 cartas de baralho, pelo menos duas são do mesmo naipe;

iv. Na cidade de Fortaleza, existem pelo menos duas pessoas com o mesmo número de fios de cabelo.

Agora vamos ver como algo tão simples pode resolver problemas aparentemente difíceis:

Problema 1. Escolhem-se 5 pontos ao acaso sobre a superfície de um quadrado de lado √2. Mostre que pelo menos dois desses pontos estão a uma distância menor que ou igual a 2.

Solução. Divida o quadrado em quatro quadrados menores. Como temos cinco pontos e quatro quadrados, teremos pelo menos dois pontos no mesmo quadradinho. Como a maior distância entre dois pontos do mesmo quadradinho não supera a medida de sua diagonal, o resultado segue de imediato.

Passo de mágica?

Para o aluno iniciante a solução do problema anterior pode ser parecida um pouco mágica. Vamos mostrar que não é bem assim, que existe um método na solução de alguns problemas simples que usam a ideia da casa dos pombos.

A primeira coisa que devemos aprender a reconhecer é quando se trata de um problema sobre casa dos pombos. Isso pode ser adquirido com experiencia, mas vamos dar um empurrãozinho. Um problema de princípio da casa dos pombos (PCP) tem quase sempre a seguinte cara:

Dado um conjunto de n objetos, prove que podemos escolher k deles satisfazendo uma propriedade.

Bem, depois de identificar que o enunciado do problema nos traz a ideia de usar PCP, devemos nos concentrar em responder às seguintes perguntas:

i. Quem são os pombos?

ii. Quantas são as casas?

iii. Quem são as casas?

Quase sempre as duas primeiras perguntas são as mais fáceis de serem respondidas. Para responder a terceira pergunta devemos pensar no conceito dual de espaço amostral. Por um lado, o espaço amostral é o conjunto das possíveis posições dos pombos. Por outro, a união de todas as casas.

Para finalizar, devemos separar o espaço amostral no número de casas já descoberto. Nessa hora é importante lembrar que as casas devem refletir a propriedade desejada.

Como acabamos de ver, usar o princípio da casa dos pombos não é difícil. O difícil está em achar o que serão nossos “pombos” e “caixas”.

Problema 2. Em um grupo de k pessoas, pelo menos duas delas terão de aniversariar no mesmo mês. De acordo com o princípio da casa dos pombos, qual deve ser o menor valor de k?

Solução: Como são 12 os meses do ano e queremos o valor mínimo de k, teremos, pelo princípio da casa dos pombos, que k deverá ser igual a 13.

Problema 3. Quantas pessoas devemos tomar, em um grupo, no mínimo, de modo que possamos garantir que duas delas nasceram no mesmo dia da semana?

Solução: Analogamente ao problema anterior, como são 7 os dias da semana, devemos ter um mínimo de oito pessoas no grupo (7 + 1).

Problema 4. Quantas pessoas devemos tomar, em um grupo, no mínimo, de modo que possamos garantir que três delas nasceram no mesmo dia da semana?

Solução: Temos agora a proposta de que possamos garantir que três dessas pessoas nasceram no mesmo dia da semana. Teremos nesse caso um mínimo de 15 pessoas (2 × 7 + 1).

Problema 5. Em uma caixa há 12 meias brancas e 12 meias pretas. Quantas meias devemos retirar, ao acaso, no mínimo, para que possamos garantir que retiramos um par de meias de mesma cor?

Solução: As quantidades de meias que estão registradas nesse exemplo só servem para nos confundir, pois se queremos obter um par de meias de mesma cor, teremos que retirar no mínimo três meias, já que só existem duas cores distintas.

Problema 6. Qual o número mínimo de pessoas que deve haver em um grupo para que possamos garantir que nele haja, pelo menos, 5 pessoas nascidas no mesmo mês?

Solução: Devemos ter nesse grupo um mínimo de 49 pessoas, pois nesse caso, até 48 pessoas ainda não poderíamos garantir que 5 delas teriam nascido no mesmo mês, 12 meses × 4 = 48 pessoas.

[Contato: macolins@gmail.com]