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

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

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