Artigos recentes

Navigation

Princípio de Dirichlet, Princípio das Gavetas ou Princípio da Casa de Pombos

Um princípio aparentemente singular que permite resolver problemas que parecem complicados.
Se você ainda não conhece o princípio de Dirichlet, você poderá se surpreender o que um raciocínio tão simples se aplica na resolução de problemas que parecem complicadíssimos e sem solução.

Em 1834, o matemático alemão Johann Peter Gustav Lejeune Dirichlet (1805-1859), criador do conceito moderno de função, enunciou o seguinte princípio, apelidado de Princípio da Casa de Pombos:
Seja dada uma casa de pombos com $n$ buracos e suponha que haja $m$ pombos querendo ocupá-los. Se $m > n$, então algum buraco deverá ser ocupado por mais de um pombo.
Princípio de Dirichlet, Princípio das Gavetas ou Princípio da Casa de Pombos

Isso parece realmente óbvio, pois tem todo o respaldo da nossa experiência do dia a dia. Este princípio também leva o nome de Princípio das Gavetas, pois pode ser reescrito, de modo equivalente:

Teorema (Princípio de Dirichlet). Queremos guardar $m$ objetos em $n$ gavetas. Se $m$ > $n$, então alguma gaveta deverá conter mais de um objeto.

Demonstração por Indução matemática sobre o número $n$ de gavetas.

Para $n = 1$, o resultado é óbvio, pois se temos mais de um objeto e uma só gaveta, teremos que acomodar nesta gaveta mais de um objeto.

Suponha então que o resultado válido para um certo número $n$ de gavetas e consideremos a situação de termos $n + 1$ gavetas e $m$ > $n + 1$ objetos. Queremos mostrar que o resultado vale também neste caso, para a plicar a Indução Matemática e concluir que vale para todo número natural $n$.

Depois de acomodar todos os objetos nas $n + 1$ gavetas, escolha uma gaveta ao acaso. Se nesta gaveta há mais de um objeto, a nossa asserção está provada. Se nesta gaveta não há nenhum objeto, nas gavetas restantes estão acomodados $m$ > $n + 1$ > $n$ objetos, o que pela hipótese de indução, acarreta que em uma das gavetas há mais de um objeto. Se na gaveta escolhida há um objeto, logo, nas n gavetas restantes, estão distribuídos $m - 1$ > $n$ objetos, o que, novamente, pela hipótese de indução, acarreta que em uma das gavetas há mais de um objeto.

Portanto, pelo Princípio de Indução Finita (Indução Matemática), há mais de um objeto em pelo menos uma das gavetas.


Rescrita. Se $n + 1$ ou mais objetos são colocados em n ou menos gavetas, então pelo menos uma gaveta recebe mais de um objeto ($n < m$).

Demonstração direta. O número médio de objetos pro gaveta é maior que ou igual a $\frac { n+1 }{ n }$, que é maior que $1$. Logo, em alguma gaveta haverá um número de objetos maior que $1$.


Exemplos de Situações em que o Princípio se Aplica


# Mostrar que todo número inteiro $n$ tem um múltiplo que se escreve apenas com os algarismos $0$ e $1$.

# Tomando $5$ pontos sobre a superfície de um quadrado de lado $2$ é possível mostrar que há dois desses pontos tais que a distância entre eles é menor que ou igual a $\sqrt { 2 }$.

# Encontrar o número mínimo de pessoas que devem estar reunidas para que se possa afirmar que nesta reunião há pelo menos $3$ pessoas que fazem aniversário no mesmo mês.

# Mostrar que em qualquer conjunto de $8$ inteiros há sempre dois deles cuja diferença é um múltiplo de $7$.

# Mostrar que em toda reunião de $n$ pessoas há sempre duas pessoas com o mesmo número de conhecidos.

# Mostrar que existe um múltiplo de $1.997$ que tem todos os dígitos iguais a $1$.

# $40.100$ candidatos estão fazendo uma prova de $20$ questões de múltipla escolha, com $5$ alternativas por questão. Suponha que nenhum candidato deixe de responder a nenhuma questão. Considere a afirmação: Pelo menos $k$ candidatos responderão de modo idêntico às $4$ primeiras questões da prova . Determine o maior valor de $k$ para o qual a afirmação é certamente verdadeira.

# Quantas vezes é preciso jogar um dado de $6$ faces, para que se garanta que uma mesma face apareça duas vezes?

# Os pontos de uma reta são coloridos com $11$ cores. Mostrar que é possível achar dois pontos com a mesma cor tal que a distância entre eles é um número inteiro.

# Na região metropolitana de São Paulo, existem pelo menos duas mulheres com a mesma quantidade de fios de cabelo, o mesmo ocorre com pelo menos dois homens. Os dados do PNAD (2004), afirmam que o máximo de fios de cabelos que uma pessoa pode ter é $7\cdot { 10 }^{ 6 }$ e existem  $10\cdot { 10 }^{ 6 }$ mulheres e $9\cdot { 10 }^{ 6 }$.

# Se cada ponto do plano é pintado de vermelho ou azul, então algum retângulo no plano tem seus vértices de uma mesma cor.

# Existem duas potências de $3$ cuja diferença é divisível por $2.007$.

# Suponha que $n + 1$ inteiros são tomados ao acaso dentre os inteiros $1, 2, ..., 2n$, pelo menos um desses inteiros é múltiplo de um outro.


Confira a sugestão destes dois vídeos sobre o Princípio:


Referências e Recomendações


MORGADO. Augusto César, CARVALHO, Paulo Cezar Pinto. Matemática Discreta. SBM, 1ª Edição. Rio de Janeiro, 2014.

O Princípio da Casa dos Pombos. Blog: Fatos Matemáticos. Confira mais sobre o Princípios e outros exemplos de aplicação.


Charles Bastos

Comente este artigo:

2 comentários:

  1. engraçado como os maiores problemas às vezes podem ser resolvidos com raciocínios simples!!!
    adorei a informação

    ResponderExcluir
    Respostas
    1. "E não é!"

      Tive a mesma sensação quando comecei a estudar o Princípio, foi algo meio corrido, ainda não vimos muito sobre ele, mas é bem simples mesmo. Só que os raciocínios para resolver determinadas situações, são bem elaborados, limpos e 'bonitos'... "Fico pensando, como é que foram pensar em algo do tipo para resolver isto?"
      É a Matemática!

      Obrigado por registrar sua presença aqui no blog!

      Excluir