O PRINCÍPIO DA CASA DOS POMBOS - 01

O Princípio da Casa dos Pombos

O princípio da casa dos pombos afirma que se tivermos  casas para acomodar  pombos, então podemos afirmar que existe uma casa com  pombos. Este princípio matemático é devido ao matemático alemão Dirichlet que o relatou em  e é também conhecido por princípio das gavetas.

Com este princípio tão simples é possível resolver vários exercícios curiosos. Vejamos alguns exemplos:

1) Se tivermos um grupo de  pessoas, então com certeza duas delas fazem aniversário no mesmo mês e se grupo aumentar para  pessoas, podemos afirmar também que existem no mínimo duas pessoas que fazem aniversário no mesmo dia.

Solução: Pelo princípio da casa dos pombos, se houvesse mais pessoas  do que meses  é certo que pelo menos duas pessoas terão nascido no mesmo mês e a explicação é análoga para o dia do mês.

2) Dado um cubo de lado , mostre que ao marcarmos pontos em seu interior, a distância entre pelo menos dois deles é menor ou a .

Solução: Para cada par de faces opostas desse cubo, tomamos um plano paralelo a essas faces e que passa pelo centro do cubo. Serão planos que dividirão esse cubo em  cubinhos de arestas .

Cada um desses cubinhos será uma casa dos pombos e como temos  pontos, então pelo menos  pontos estarão no interior ou na superfície um cubo de aresta . Sendo a maior distância entre dois pontos quaisquer num desses cubinhos igual ao comprimento da diagonal do cubo, ou seja, , temos o resultado desejado.

3) Todos os pontos de um plano são pintados de azul ou vermelho. Prove que podemos encontrar dois pontos da mesma cor que distam exatamente .
Solução: Basta imaginarmos um triângulo equilátero de lado igual a . Como são duas cores (casas) e três pontos (pombos). Pelo princípio da casa dos pombos teremos dois da mesma cor.
Embora este princípio parece simples, mas é através dele que pode demonstrar resultados possivelmente inesperados. Por exemplo, em qualquer grande cidade (digamos com mais de 1 milhão de habitantes) existem pessoas com o mesmo número de fios de cabelo.
Para finalizar, apresento a seguir outros problemas que podem ser resolvidos através do princípio da casa dos pombos, cuja solução é deixada como exercício.

1) Quantos estudantes devem ter em numa turma para garantir que pelo menos dois estudantes possuam a mesma nota no exame final, se a nota do exame varia de  a ?

2) Mostre que entre um grupo de  inteiros (não necessariamente consecutivos) existem dois com o mesmo resto quando divididos por .

3) Seja  um inteiro positivo. Mostre que entre qualquer grupo de  inteiros (não necessariamente consecutivos) existem dois com exatamente o mesmo resto quando divididos por .

Referência Bibliográfica:1) Blog Cultura e Lazer
2) Oliveira, Anjolina Grisi de. Princípio da Casa dos Pombos. Centro de Informática, UFPE.