FANDOM


O Princípio das Casas dos Pombos (ou teorema de Dirichlet ou Princípio das Gavetas de Dirichlet) é a afirmação de que se $ n $ pombos forem ser postos em $ m $ casas, e $ n>m $, 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.

ExemploEditar

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)Editar

Dentre os polígonos de $ 5 $ 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 $ 12 $ lados pode ter?

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

OBM2006q2n21

Mostraremos que não conseguimos desenhar um polígono com $ 9 $ ou mais vértices alinhados. Para facilitar a escrita, chamaremos os vértices do polígono, na ordem que eles aparecem, de $ V_1,V_2,\dots,V_{12} $.

Vamos definir

$ G_1=\{V_1,V_2,V_3\} $

$ G_2=\{V_4,V_5,V_6\} $

$ G_3=\{V_7,V_8,V_9\} $

$ G_4=\{V_{10},V_{11},V_{12}\} $.

Se escolhermos $ 9 $ vértices para pertencer a uma reta, pelo menos, algum dos conjuntos $ G_1, G_2, G_3, G_4 $ 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 é $ 8 $.

Generalização Editar

É 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 $ mn+1 $ objetos e quisermos colocar em $ m $ gavetas, então alguma delas terá pelo menos $ n+1 $ objetos.
  • Se tiveremos que colocar $ n $ objetos em $ k $ gavetas, então alguma gaveta terá um número maior ou igual a $ \lfloor \frac{n-1}{k}\rfloor+1 $ de objetos.

Exemplo Editar

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 $ 3 $ objetos.

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

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

$ \left\lfloor \frac{2x+1-1}{x}\right\rfloor+1=\left\lfloor \frac{2x}{x}\right\rfloor+1=\left\lfloor 2\right\rfloor+1=2+1=3. $

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

No interior de um quadrado de lado $ 16 $ são colocados $ 1000 $ pontos. Mostre que é possível colocar um triângulo equilátero de lado $ 2\sqrt{3} $ no plano de modo que ele cubra pelo menos $ 16 $ 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 $ 16 $ desses pontos.

Como o lado do triângulo mede $ 2\sqrt{3} $, sua altura será $ \frac{2\sqrt{3}\sqrt{3}}{2}=3 $. 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 $ 5 $ faixas, pois a altura seria $ 3.5=15 $ que é menor que $ 16 $ (o lado do quadrado). Porém podemos cobrir usando $ 6 $ dessas faixas horizontalmente.

E quantos triângulos devem haver nessa faixa? Note que $ 4 $ não são suficiente para cobrir o quadrado. De fato, se tivéssemos quatro triângulos teríamos o comprimento $ 4.2\sqrt{3}=8\sqrt{3} $ que é menor que $ 16 $. Mas $ 5 $ triângulos já dão: o comprimento da faixa será $ 5.2\sqrt{3}=10\sqrt{3} $, que é maior do que $ 16 $.

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

OBM2011q5n21
Esta cobertura terá $ 11.6=66 $ triângulos.

Pelo Princípio da Casa dos Pombos, se distribuirmos $ 1000 $ pontos em $ 66 $ triângulos, algum dos triângulos terá pelo menos $ \lfloor \frac{1000-1}{6}\rfloor+1=16 $ pontos.

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

Numeramos as casas de um tabuleiro quadriculado $ m \times n $, onde $ m,n \geq 2 $, com os inteiros $ 1,2,3,\cdots,mn $ de modo que, para todo $ i \leq mn-1 $, as casas $ i $ e $ i+1 $ tenham um lado em comum.

Prove que existe $ i \leq mn-3 $ tal que as casas $ i $ e $ i+3 $ 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 $ i $ e $ i+3 $ 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 $ mn $ pontos nesta malha. Se ligarmos eles (na horizontal e vertical), teremos quantos quadradinhos menores? Vejamos um caso particular: uma malha $ 4 \times 3 $.

OBM2002q3n33

Existirão, neste caso, $ 3-1=2 $ quadrados em cada linha e $ 4-1=3 $ quadrados em cada coluna, totalizando $ 2 \cdot 3=6 $ quadrados. No caso mais geral, de uma malha $ m \times n $, teremos $ n-1 $ quadrados em cada linha e $ m-1 $ quadrados em cada coluna, totalizando $ (m-1)(n-1) $ quadradinhos menores.

Quando ligarmos os números de $ 1 $ a $ mn $ estaremos passando por cima dos lados destes quadradinhos. E observe que se houver um quadradinho com $ 3 $ lados pintados, teremos alguma das possibilidades da Figura 1. Observe que, para ligarmos os números de $ 1 $ a $ mn $, precisamos de $ mn-1 $ riscos. Portanto, para terminarmos o problema, basta mostrarmos que, ao fazer $ mn-1 $ 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 $ 1 $ 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 $ 11 $ segmentos: $ 9 $ na borda (que são contados uma vez só, pois pertencem a um quadrado) e $ 2 $ no interior (que são contados duas vezes, pois pertencem a dois quadrados). Assim o número de lados, com multiplicidade, é $ 9+2 \cdot 2=13 $.

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 $ 3 $ 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 $ p $. Como a quantidade total de riscos é $ mn-1 $, segue que a quantidade de lados no interior da malha será $ mn-1-p $. Desta forma, a quantidade de lados, com multiplicidade (contando uma vez se estiver na borda e duas vezes se estiver no interior), será

$ p+2(mn-1-p)=2mn-2-p.(*) $

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á $ 2(m-1)+2(n-1)-1=2m+2n-5 $.

Assim, o número mínimo de lados de quadrados preenchidos será o que aparece em $ (*) $ com $ p=2m+2n-5 $, ou seja,

$ 2mn-2-(2m+2n-5)=2mn-2m-2n+3. $

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

$ 2mn-2m-2n+3>\frac{4(m-1)(n-1)}{2}. $

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

$ 2mn-2m-2n+3>2mn-2m-2n+2 \Leftrightarrow 3>2. $

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

Formulação do Princípio Envolvendo Conjuntos Editar

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 injetora.

Ligações externasEditar

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

O conteúdo da comunidade está disponível sob CC-BY-SA salvo indicação em contrário.