segunda-feira, 21 de abril de 2014

PRINCÍPIO DAS GAVETAS ou PRINCÍPIO DAS CASAS DE POMBOS

Muitos problemas atraentes de matemática elementar exploram relações entre conjuntos finitos, expressas em linguagem coloquial. Parte de sua atração vem justamente do fato de que podem ser formulados e, muitas vezes, resolvidos sem recorrer a fórmulas ou a técnicas complicadas. Vejamos um exemplo simples ilustrativo desses problemas.
Exemplo: Qual é o número mínimo de pessoas que devemos reunir para que tenhamos certeza de que entre elas há pelo menos duas que fazem aniversário no mesmo mês? Solução: A resposta é 13. Se houvesse apenas 12 pessoas, seria possível que cada uma delas fizesse aniversário em um mês diferente. Com 13 pessoas, há , obrigatoriamente, pelo menos um mês com mais de um aniversário (se houvesse, no máximo, um aniversário por mês, o número de pessoas presentes seria, no máximo, 12). 

O argumento empregado acima é conhecido como PRINCÍPIO DAS GAVETAS (de Dirichlet) ou PRINCÍPIO DAS CASAS DE POMBOS. Um possível enunciado para este princípio é o seguinte: Se n objetos forem colocados em, no máximo, n ­– 1 gavetas, então pelo menos uma delas conterá pelo menos dois objetos. (Uma maneira um pouco mais formal de dizer o mesmo é: se o número de elementos de um conjunto finito A é maior do que o número de elementos de um outro conjunto B, então uma função de A em B não pode ser injetiva.) 
       (Paulo Cezar Pinto Carvalho – IMPA) Este princípio é muito recorrente em concursos públicos. 

Fonte : http://bettonunes.blogspot.com.br/2011/01/principio-das-gavetas-ou-principio-das.html



1) Se tivermos um grupo de 13 pessoas, então com certeza duas delas fazem aniversário no mesmo mês e se grupo aumentar para 32 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 13 pessoas do que meses 12 é 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 2 , mostre que ao marcarmos 9 pontos em seu interior, a distância entre pelo menos dois deles é menor ou a raiz de 3 .

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 [;3;]planos que dividirão esse cubo em [;8;]cubinhos de aresta 1.
Cada um desses cubinhos será uma casa dos pombos e como temos 9 pontos, então pelo menos 2 pontos estarão no interior ou na superfície um cubo de aresta 1. Sendo a maior distância entre dois pontos quaisquer num desses cubinhos igual ao comprimento da diagonal do cubo, ou seja raiz de 3 , 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 10 cm .
Solução: Basta imaginarmos um triângulo equilátero de lado igual a 10cm. 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.

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.
Postado por Prof. Paulo Sérgio às 25.7.09

Nenhum comentário:

Postar um comentário