Princípio da casa dos pombos

O princípio do pombal ou princípio da casa dos pombos é a afirmação de que se n pombos devem ser postos em m casas, e se n > m, então pelo menos uma casa irá conter mais de um pombo. Matematicamente falando, isto quer dizer que 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 injetiva.

A inspiração para o nome do princípio: pombos em gaiolas ("casas"). Aqui n = 10 e m = 9.

É também conhecido como teorema de Dirichlet ou princípio das gavetas de Dirichlet, pois supõe-se que o primeiro relato deste princípio tenha sido feito por Dirichlet em 1834, com o nome de Schubfachprinzip ("princípio das gavetas").

O princípio do pombal é um exemplo de um argumento de calcular que pode ser aplicado a muitos problemas formais, incluindo aqueles que envolvem um conjunto infinito.

Embora se trate de uma evidência extremamente elementar, o princípio é útil para resolver 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 1

• Quantas pessoas são necessárias para que possa garantir que há pelo menos duas delas fazendo aniversário no mesmo mês?

Resposta: 13 pessoas. Pelo princípio da casa dos pombos se houver mais pessoas (13) do que meses (12) é certo que pelo menos duas pessoas terão nascido no mesmo mês.

Exemplo 2

• Todos os pontos de um plano são pintados de amarelo ou verde. Prove que podemos encontrar dois pontos de mesma cor que distam exatamente um metro:

Solução: Basta imaginarmos um triângulo equilátero de lado igual a um metro. Como são duas cores (casas) e três pontos (pombos),pelo PCP (princípio da casa dos pombos) teremos dois de mesma cor.

Embora este princípio seja uma observação trivial, pode ser usado para demonstrar resultados possivelmente inesperados. Por exemplo, em qualquer grande cidade (digamos com mais de 1 milhão de habitantes) existem pessoas com o mesmo número de fios de cabelo. Demonstração: Tipicamente, uma pessoa tem cerca de 150 mil fios de cabelo. É razoável supor que ninguém tem mais de 1.000.000 de fios de cabelo em sua cabeça. Se há mais habitantes do que o número máximo de fios de cabelo, necessariamente pelo menos duas pessoas terão precisamente o mesmo número de fios de cabelo.

Generalizações do princípio

Uma versão generalizada declara que, se n objetos distintos para ser alocados à m recipientes, então pelo menos um recipiente deve conter não menos que $\lceil n/m\rceil$ objetos, onde $\lceil x\rceil$ denota o menor inteiro igual ou superior a x (a função tecto).

Uma generalização probabilística do princípio da casa dos pombos define que se "n" pombos são colocados aleatoriamente em "m" casas com uma probabilidade uniforme 1/m, então pelo menos uma casa de pombos terá mais de um pombo com probabilidade:

$1-{\frac {m!}{(m-n)!\;m^{n}}}=1-{\frac {m^{\underline {n}}}{m^{n}}},\!$

onde $m^{\underline {n}}$ é um fatorial decrescente até n. Para n = 0 e para n = 1 (e m > 0), que provavelmente é zero; em outras palavras, se tem apenas um pombo, então não deve haver conflitos. Para n > m (mais pombos do que casa de pombos) é um, neste caso coincide com o princípio de casa dos pombos normal. Mas mesmo que o número de pombos não exceda o número de casa de pombos (n ≤ m), devido a natureza da atribuição aleatória das casas aos pombos existe uma chance substancial que um confronto ocorra muitas vezes. Por exemplo, se 2 pombos são colocados aleatoriamente em 4 casas de pombos, há uma chance de 25% que pelo menos uma casa de pombo ter mais do que um pombo, para 5 pombos e 10 casas, a probabilidade é de 69,76%; e para 10 pombos em 20 casas a probabilidade é de 93,45%.

Caso do princípio para conjuntos infinitos

O princípio citado, quando aplicado para conjuntos infinitos, se torna falso. Isso é provado com a utilização do "Paradoxo do Grande Hotel de David Hilbert".

Esta abordagem é impossível com conjuntos infinitos, pois não há número capaz de representar a “quantidade” de elementos desses conjuntos. Portanto, para generalizar o conceito de cardinalidade a conjuntos infinitos e poder comparar o “tamanho” desses, há necessidade de lançar mão de outras caracterizações daquele conceito. Tendo definido os instrumentos formais para isso, chegamos a alguns resultados interessantes sobre conjuntos infinitos.

O princípio continuará valendo para um par de conjuntos, se pelo menos, um deles for finito e outro não.

Mecânica quântica

Dois pombos podem sentar-se confortavelmente em dois buracos, mas adicionar um terceiro pássaro e eles terão que compartilhar. Mas três partículas quânticas podem ocupar dois estados sem ter o mesmo estado sob uma condição específica.

Ligações externas

• (em inglês) Princípio do pombal na página cut-the-knot;
• (em inglês) "O estranho caso do princípio do pombal"; Edsger Dijkstra investiga as interpretações e formulações do princípio.

Ver também

• Princípios combinatórios
• Números cardinais
• Sistema infinito de Dedekind
• Paradoxo de Hilbert do grande hotel
• Teorema de Ramsey