Wiki Olimpédia
Registre-se
Advertisement

O Princípio das Casas dos Pombos (ou teorema de Dirichlet ou Princípio das Gavetas de Dirichlet) é a afirmação de que se pombos forem ser postos em casas, e , então pelo menos uma casa irá conter mais de um pombo.

O primeiro relato deste princípio teria sido feito pelo matemático alemão Dirichlet em 1834, com o nome de Schubfachprinzip ("princípio das gavetas").

Embora se trate de uma evidência bem elementar, o princípio é útil para resolvermos 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[]

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: Pelo Princípio das Casas dos Pombos, se houver mais pessoas do que meses, é certo que pelo menos duas pessoas terão nascido no mesmo mês (note que os meses são as "casas" e as pessoas são os "pombos"). Como existem 12 meses, segue que são necessárias 13 pessoas.

Exemplo (OBM 2006 - 3ª Fase - Nível 2)[]

Dentre os polígonos de lados, o maior número possível de vértices alinhas, isto é, pertencentes a uma única reta, é três, como mostrado a seguir.

OBM2006q1n2

Qual é a maior quantidade de vértices alinhados que um polígono de lados pode ter?

Solução: Conseguimos um polígono com vértices em uma mesma reta.

OBM2006q2n21

Mostraremos que não conseguimos desenhar um polígono com ou mais vértices alinhados. Para facilitar a escrita, chamaremos os vértices do polígono, na ordem que eles aparecem, de .

Vamos definir

.

Se escolhermos vértices para pertencer a uma reta, pelo menos, algum dos conjuntos terá todos os seus vértices escolhidos. Isto não pode ocorrer, pois aí, teríamos três vértices consecutivos colineares. Logo, o máximo de polígonos que devem pertencer à reta é .

Exemplo[]

Sejam inteiros positivos. Prove que existem , com , de forma que é um múltiplo de .

Solução: Os restos da divisão de um número por são , ou seja, há restos possíveis.

Considere os números . Se há algum múltiplo de dentre esses números, encontramos o que o enunciado pede e o problema acabou. Caso contrário, há apenas restos possíveis (que são ) para encaixarmos em números. Ou seja, pelo Princípio das Casas dos Pombos, há dois números que têm o mesmo resto na divisão por . Suponha que sejam eles e , com .

Como os dois têm o mesmo resto na divisão por , o número é múltiplo de , e é igual a:

Como é um múltiplo de , encontramos o que queríamos encontrar.

Exemplo (IMO 2009)[]

Sejam inteiros positivos distintos e um conjunto de inteiros positivos que não contém o número . Um gafanhoto pretende saltar ao longo da reta real. Ele começa no ponto e dá saltos para a direita de comprimentos , em alguma ordem.

Prove que essa ordem pode ser escolhida de modo que o gafanhoto nunca caia num ponto de .

Solução: Vamos usar indução forte em .

Neste caso, o conjunto possui elemento, ou seja, ele é vazio, logo o gafanhoto nunca estará em um elemento dele.

  • Suponha que a afirmação seja verdadeira para . Vamos provar que ela é válida também para .

Em casos de indução, a ideia principal é reduzir a casos menores. A primeira coisa que vale a pena tentarmos mexer aqui é o primeiro obstáculo que o gafanhoto irá encontrar, ou seja, o primeiro elemento de que o gafanhoto deverá passar por cima. Observe que esse é o menor elemento de . Como ele é importante, chamaremos de .

O pulo que tem mais chance de "pular por" é o maior pulo possível do gafanhoto. Mas qual dos pulos é o maior possível? Como não sabemos, podemos supor, sem perda de generalidade, que . Caso isso não aconteça, basta renomearmos os pulos. Vamos pensar no maior pulo do gafanhoto, ou seja, . Será que esse pulo passa por (isto é, ) ou não (isto é )? Vamos analisar cada caso separadamente.

1º Caso:

Existem também duas possibilidades aqui: após o pulo de tamanho estar em um número que está em (ou seja, ser elemento de ) ou estar fora de . Analisemos cada caso separadamente.

(i) não é elemento de

Conseguimos reduzi a um caso menor aqui. De fato, se ela der o primeiro pulo de tamanho , ela reduzirá a pulos de tamanhos e ao conjunto que possui elementos, ou seja, ela reduziu ao caso . Por hipótese de indução, existe uma sequência de pulos que o gafanhoto pode fazer.

(ii) é elemento de

Neste caso, não pode ser o primeiro pulo (já que ele pertence a ). Mas será que ele pode ser o segundo? Para isso acontecer, devemos ter e fora de para algum . Será que isso pode acontecer? Suponha que, dentre os pares , todos eles tem pelo menos um elemento em . Só que existiriam elementos para "caberem" em um conjunto de elementos. Isso não pode acontecer. Logo algum desses pares, digamos, tem seus dois elementos fora de . Assim, o gafanhoto pode dar dois pulos de tamanhos e (nesta ordem) e esses pulos não "caírem" em .

Repare que ao fazer isso, os gafanhotos "pulam por cima de" e que são elementos de (de fato, ). Assim, o gafanhoto terá que dar outros pulos e não passar pelo conjunto que possui elementos. Aqui entramos no caso que, por hipótese de indução, é possível.

2º Caso:

Neste caso, mesmo que o gafanhoto dê seu maior pulo, ele não passará por cima do primeiro elemento de . Já que o começo do trajeto do gafanhoto parece meio conturbado, talvez vale a pena pensarmos no final. Vamos pensar no gafanhoto saindo do último ponto e fazendo os seus pulos ao contrário (aqui podemos usar a hipótese de indução de alguma forma, imaginando que o invés de , o gafanhoto esteja no zero e ao invés de ir para a esquerda, ele vai para a direita).

Pensemos nele fazendo pulos (para podermos usar a hipótese de indução): . Pela própria hipótese de indução, ele consegue evitar todos os pontos de (já que esse conjunto possui elementos). Repare que ao fazer esse processo, o gafanhoto irá parar em . Se ele não passar por , o problema estará resolvido.

Suponha, agora, que, depois de ter feito um pulo de tamanho , ele pouse sobre . Basta mudarmos o pulo de tamanho para um de tamanho , pois aí ele não pousará em (já que e ele dará um pulo maior). Todos os próximos pulos não pousarão em ninguém de (já que a esquerda de não temos nenhum elemento do conjunto). Desta forma, conseguimos resolver esse caso também.

Generalização[]

É ideal que, para ler esta parte, você saiba a definição e um pouco sobre as propriedades da função parte inteira. Podemos pensar de duas maneiras:

  • Se tivermos objetos e quisermos colocar em gavetas, então alguma delas terá pelo menos objetos.
  • Se tivermos que colocar objetos em gavetas, então alguma gaveta terá um número maior ou igual a de objetos.

Exemplo[]

Suponha que iremos guardar alguns objetos em algumas gavetas. Prove que se a quantidade de gavetas for menor do que a metade da quantidade de objetos, então alguma gaveta ficará com pelo menos objetos.

Solução: Vamos supor que existam gavetas. Como a quantidade de gavetas é menor do que a metade da quantidade de objetos, existem mais do que objetos, ou seja, pelo menos .

Mostraremos que ao guardar objetos em gavetas, então, pelo menos alguma gaveta terá pelo menos objetos. De fato, pelo Princípio da Casa dos Pombos, alguma gaveta terá uma quantidade de objetos maior ou igual a

Exemplo (OBM 2011 - 3ª Fase - Nível 2)[]

No interior de um quadrado de lado são colocados pontos. Mostre que é possível colocar um triângulo equilátero de lado no plano de modo que ele cubra pelo menos destes pontos.

Solução: Vamos começar encontrando a quantidade de triângulos necessária para cobrir (e até podendo ultrapassar) o quadrado. Depois usaremos o Princípio da Casa dos Pombos para mostrar que pelo menos algum desses triângulos cobrirá pelo menos desses pontos.

Como o lado do triângulo mede , sua altura será . Considere o seguinte esquema.

OBM2011q5n2

Primeiramente, descobrimos quantas dessas faixas podemos colocar horizontalmente na figura e depois calcularemos quantos triângulos existirão nesta faixa. Observe que não podemos colocar faixas, pois a altura seria que é menor que (o lado do quadrado). Porém podemos cobrir usando dessas faixas horizontalmente.

E quantos triângulos devem haver nessa faixa? Note que não são suficiente para cobrir o quadrado. De fato, se tivéssemos quatro triângulos teríamos o comprimento que é menor que . Mas triângulos já dão: o comprimento da faixa será , que é maior do que .

Desta forma, as faixas devem possuir triângulos ( deles virados para cima e para baixo) conforme ilustra a figura a seguir.

OBM2011q5n21

Esta cobertura terá triângulos.

Pelo Princípio da Casa dos Pombos, se distribuirmos pontos em triângulos, algum dos triângulos terá pelo menos pontos.

Exemplo (IMO 1964)[]

Em um grupo de alunos, todos eles conversaram com todos os outros sobre algum tópico. Todos eles conversaram sobre três tópicos diferentes. Cada par de alunos conversou sobre apenas um tópico. Prove que existe um trio de alunos que falaram apenas sobre um tópico um com o outro.

Solução: Sejam , e os tópicos. Vamos considerar como os alunos. Considere as 16 conversas tidas pelos pares , e três tópicos possíveis no total, que representam 16 pombos para serem colocados em 3 casas, o que significa que há um tópico que foi discutido em pelo menos conversas.

Suponhamos, então, sem perda de generalidade que são conversas que trataram de . Se alguma das conversas entre for sobre , então há um trio que só falou de e o problema acabou. Então, suponhamos que todas elas são sobre e . Vamos considerar as conversas entre os pares e os tópicos e . Temos 5 pombos e 2 casas, o que significa que há um tópico que foi discutido em pelo menos conversas.

Vamos supor, então, que as conversas são todas sobre . Se alguma das conversas for sobre , haverá um trio que fala só sobre . Caso contrário, todas elas deverão falar sobre e será um trio que só fala sobre um assunto, ou seja, sempre há um desses trios e o problema acabou.

O problema é equivalente provar que, pintando as arestas de um grafo completo de 17 vértices com 3 cores, teremos sempre pelo menos um triângulo monocromático.

Exemplo[]

a) Quatro números inteiros positivos somam . Prove que há pelo menos um deles que é maior que .

b) números inteiros positivos tem uma soma maior do que . Prove que há pelo menos um deles que é maior que .

Solução:

a) Imagine que temos números s para encaixar nessas quatro parcelas da soma. Pelo princípio das casas dos pombos, há uma parcela com pelo menos números s nela, ou seja, há uma parcela maior que .

Também podemos resolver esse problema supondo, por absurdo, que todas as parcelas são menores que ou iguais a , dessa forma, a soma de todas elas será menor que ou igual a , o que é de fato um absurdo.

b) Vamos proceder como no item anterior: imagine que temos um número maior que de números s para encaixar nessas parcelas. Pelo Princípio das Casas dos Pombos, haverá uma parcela com mais do que números s nela, então há uma parcela maior que .

Podemos pensar por absurdo também: se as parcelas fossem menores que ou iguais a , então a soma delas seria menor que ou igual a . Então há pelo menos uma parcela que é maior que .

Esse resultado pode parecer bobo, mas ajuda a entender a solução do próximo problema.

Exemplo (OBM 2017 - Nível 2)[]

Seja um inteiro e considere um tabuleiro , em que algumas das casas foram pintadas de preto, e as restantes foram pintadas de branco. Prove que é possível escolhermos uma das casas do tabuleiro, de modo que, ao removermos completamente a linha e a coluna que a contém, haja um número diferente de casas pretas e de casas brancas, dentre as casas restantes.

Solução: Vamos imaginar a situação que queremos evitar: um tabuleiro com casas pretas e casas brancas. Esse tabuleiro tem casas, o que significa que os tabuleiros que temos que evitar sempre têm um número par de casas.

Então, prestemos atenção no que a nossa operação de remover linhas e colunas faz com o número de casas do tabuleiro: se começarmos com um tabuleiro com casas, depois ficaremos com casas: note que esses dois números têm paridades diferentes, o que, junto com o que acabamos de delimitar, significa duas coisas:

  • Podemos escolher qualquer casa em um tabuleiro com um número par de casas, porque o tabuleiro resultante terá um número ímpar de casas e é impossível ter um número igual de casas pretas e brancas.
  • Devemos nos preocupar, portanto, apenas com fazer a operação casas em tabuleiros com um número ímpar de casas.

Vamos supor, então, que temos um tabuleiro com casas, ímpar. Suponha que há mais casas pretas do que brancas, e seja o número de casas pretas. Assim, .

Sejam todas as casas do tabuleiro e vamos chamar de o tanto de casas pretas que restam no tabuleiro após fazer a operação de remoção com . Queremos provar que pelo menos um dos é diferente de ; como as casas pretas estão em maior quantidade, parece que vale a pena provar que existe um dos que é maior que . Que tal usarmos o exemplo anterior? Se somarmos todos os , estaremos contando quantas casas pretas não compartilham uma linha ou coluna com cada uma das casas, e depois somamos todas as contagens. Então, como cada casa preta tem casas que não compartilham linhas ou colunas com ela, cada casa preta está sendo contada vezes. Dessa forma:

Podemos finalizar o problema de duas formas; ou melhor, podemos raciocinar sobre como ele termina de duas formas.

Método 1: Como estabelecemos, . Portanto:

Como há parcelas na direita e a soma delas é maior que , então alguma das parcelas deve ser maior que , ou seja, existe pelo menos um dos que é maior que , ou seja, existe uma casa na qual fazemos uma operação e o número das casas pretas é maior que o número das casas brancas.

Método 2: Suponha, por absurdo, que não exista uma casa em que fazemos a operação e ficamos com um número diferente de casas pretas e brancas. Então todos os devem ser exatamente iguais a . Mas, daí, temos:

Mas é um absurdo, portanto existe uma casa em que podemos fazer a operação.

Exemplo (OBM 2002 - 3ª Fase - Nível 3)[]

Numeramos as casas de um tabuleiro quadriculado , onde , com os inteiros de modo que, para todo , as casas e tenham um lado em comum.

Prove que existe tal que as casas e têm um lado em comum.

Solução: A estratégia aqui será transformar o problema em outro que seja mais interessante de resolver. Para isto, temos que enxergá-lo de outra forma. Observe que podemos pensar na numeração da tabela como uma preenchimento de uma malha de pontos. Como? Vamos imaginar setas unindo números consecutivos. Por exemplo,

OBM2002q3n3

Podemos agora pensar nisto sem os números e no lugar dos quadradinhos, podemos imaginar os seus centros. Teremos assim a seguinte figura.

OBM2002q3n31

Ou seja, preencher a tabela conforme o enunciado é equivalente a ligar todos os pontos de uma malha com uma linha única (sem "quebras" ou bifurcações).

E como seria a ideia de e terem um lado em comum no caso das malhas? Isto acontecerá se qualquer uma das figuras a seguir aparecer na nossa malha:

OBM2002q3n32

Figura 1

Assim o problema que precisamos resolver é outro: o de provar que é impossível preencher a malha sem fazer aparecer uma das figuras acima.

Vamos entender um pouco melhor a figura. Existem pontos nesta malha. Se ligarmos eles (na horizontal e vertical), teremos quantos quadradinhos menores? Vejamos um caso particular: uma malha .

OBM2002q3n33

Existirão, neste caso, quadrados em cada linha e quadrados em cada coluna, totalizando quadrados. No caso mais geral, de uma malha , teremos quadrados em cada linha e quadrados em cada coluna, totalizando quadradinhos menores.

Quando ligarmos os números de a estaremos passando por cima dos lados destes quadradinhos. E observe que se houver um quadradinho com lados pintados, teremos alguma das possibilidades da Figura 1. Observe que, para ligarmos os números de a , precisamos de riscos. Portanto, para terminarmos o problema, basta mostrarmos que, ao fazer riscos, algum dos quadrados terá três lados com riscos.

Para prosseguir o raciocínio, vamos contar a quantidade de lados dos quadrados com multiplicidade. Como funciona isto? Vejamos o seguinte exemplo.

OBM2002q3n34

Figura 2

Observe que se um risco for feito na "borda" da malha, ele preencherá apenas lado de quadrado.

OBM2002q3n35

Já se o risco for feito no "interior" da malha, preencherá dois lados de quadrados.

OBM2002q3n36

Observe que, na figura 2, existem segmentos: na borda (que são contados uma vez só, pois pertencem a um quadrado) e no interior (que são contados duas vezes, pois pertencem a dois quadrados). Assim o número de lados, com multiplicidade, é .

Baseado em um exemplo anterior, se provarmos que o número de lados (com multiplicidade) que o caminho irá passar for maior do que a metade de lados totais dos quadradinhos menores, então algum lado irá ter dos seus lados riscados. Ou seja, ao mostrarmos este fato, terminaremos o problema.

A estratégia aqui será minimizar a quantidade de lados dos quadrados (com multiplicidade) e provar que este valor mínimo ainda é maior do que a metade de lados totais dos quadradinhos menores.

Mas antes de minimizar, vamos descobrir como contar a quantidade de lados (com multiplicidade). Isto vai depender da quantidade de lados da borda. Vamos supor que esta quantidade seja . Como a quantidade total de riscos é , segue que a quantidade de lados no interior da malha será . Desta forma, a quantidade de lados, com multiplicidade (contando uma vez se estiver na borda e duas vezes se estiver no interior), será

E como minimizar a quantidade de lados (com multiplicidade)? Basta maximizarmos a quantidade de lados riscados na borda. Esta quantidade é máxima quando todos os lados da borda forem riscados, com exceção de um (afinal, não podemos dar uma volta completa). Ou seja, a quantidade de riscos na borda máxima será .

Assim, o número mínimo de lados de quadrados preenchidos será o que aparece em com , ou seja,

Desta maneira, para terminarmos, basta mostrarmos que esta quantidade é maior do que a metade to total de lados (com multiplicidade). Como existem quadrados e cada um tem lados, segue que esta quantidade é . Precisamos, então, mostrar que

Para isto, vamos reescrever esta equação de forma que ela seja equivalente a alguma verdadeira. Observe que esta equação pode ser reescrita como

Como isto é sempre verdadeiro, segue sempre existirá um quadrado que terá três de seus lados riscados e assim algum existirá tal que e estão lado a lado na tabela.

Formulação do Princípio Envolvendo Conjuntos[]

Se o número de elementos de um conjunto finito é maior do que o número de elementos de um outro conjunto , então uma função de em não pode ser injetora.

Ligações externas[]

Texto 002: Princípios das Casas de Pombos - Clubes de Matemática da OBMEP

Lugares Para Estudar[]

Vídeos[]

Advertisement