O Princípio da Casa dos Pombos ou Princípio das Gavetas de Dirichlet nos diz que para colocarmos $n+1$ pombos em $n$ gaiolas , pelo menos uma gaiola deverá conter pelo menos dois pombos.
Este princípio , embora bastante intuitivo e de fácil compreensão , pode ser uma ferramenta poderosa na solução de problemas difíceis da matemática.
Vamos ilustrar uma aplicação do Princípio da Casa dos Pombos na teoria dos números.
Exemplo
Mostrar que todo subconjunto de $\{1,2,\cdots , 2n\}$ contendo $n+1$ elementos , possui um par de elementos primos entre si.
Basta notar que os únicos subconjuntos de $\{1,2,\cdots , 2n\}$ contendo $n$ elementos , não-consecutivos , são $\{1,3,\cdots , 2n-1\}$ e $\{2,4,\cdots , 2n\}$. Logo , se tomarmos um subconjunto com $n+1$ elementos, de fato , teremos dois elementos consecutivos e como o máximo divisor comum de dois números consecutivos é $1$ , concluímos que estes números são primos entre si.
Referências
Introdução à Teoria dos Números
José Plínio de Oliveira Santos
Nenhum comentário:
Postar um comentário