O princípio do pombal ou princípio da casa dos pombos é a afirmação de 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. 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 um outro conjunto B, então uma função de A em B não pode ser injetiva. É também conhecido como teorema de Dirichlet ou princípio das gavetas de Dirichlet, pois supõe-se que o primeiro relato deste principio foi feito por Dirichlet em 1834, com o nome de Schubfachprinzip ("princípio das gavetas"). O princípio do pombal é um exemplo de um argumento de calcular que pode ser aplicado em muitos problemas formais, incluindo aqueles que envolvem um conjunto infinito. Embora se trate de uma evidência extremamente elementar, o princípio é útil para resolver problemas que, pelo menos à primeira vista, não são imediatos. Para aplicá-lo, devemos identificar, na situação dada, quem faz o papel dos objetos e quem faz o papel das gavetas.
Exemplo 1:Quantas pessoas são necessárias para se ter certeza que haverá pelo menos duas delas fazendo aniversário no mesmo mês?
Solução: 13 pessoas. Pelo princípio da casa dos pombos se houver mais pessoas (13) do que meses (12) é certo que pelos menos duas pessoas terão nascido no mesmo mês.
Exemplo 2: Todos os pontos de um plano são pintados de amarelo ou verde. Prove que podemos encontrar dois pontos de mesma cor que distam exatamente um metro.
Solução: Basta imaginarmos um triângulo equilátero de lado igual a um metro. Como são duas cores (casas) e três pontos (pombos),pelo PCP (princípio da casa dos pombos) teremos dois de mesma cor.
Solução: 13 pessoas. Pelo princípio da casa dos pombos se houver mais pessoas (13) do que meses (12) é certo que pelos menos duas pessoas terão nascido no mesmo mês.
Exemplo 2: Todos os pontos de um plano são pintados de amarelo ou verde. Prove que podemos encontrar dois pontos de mesma cor que distam exatamente um metro.
Solução: Basta imaginarmos um triângulo equilátero de lado igual a um metro. Como são duas cores (casas) e três pontos (pombos),pelo PCP (princípio da casa dos pombos) teremos dois de mesma cor.
* * * * *
NOTA: Embora este princípio seja uma observação trivial, pode ser usado para 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. Demonstração: Tipicamente uma pessoa tem cerca de 150 mil fios de cabelo. É razoável supor que ninguém tem mais de 1.000.000 de fios de cabelo em sua cabeça. Se há mais habitantes do que o número máximo de fios de cabelo, necessariamente pelo menos duas pessoas terão precisamente
o mesmo número de fios de cabelo.
Nenhum comentário:
Postar um comentário