Princípio da Casa dos Pombos
Origem: Wikipédia, a enciclopédia livre.
O princípio da Casa dos Pombos é a afirmação de que se n pombos devem ser postos em m casas, sendo n > m então pelo menos uma casa irá conter mais de um pombo.
É também conhecido como Princípio das Gavetas de Dirichlet, acredita-se que o primeiro relato deste principio foi feito por Dirichlet em 1834, com o nome de Schubfachprinzip ("Princípio das Gavetas").
O princípio da casa do pombo é um exemplo de um argumento de calcular que pode ser aplicado em muitos problemas formais, incluindo aqueles que envolvem um conjunto infinito.
[editar] Exemplo
- Quantas pessoas são necessárias para se ter certeza que haverá pelo menos duas delas façam 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 pelos menos duas pessoas terão nascido no mesmo mês.
Embora o princípio da casa dos pombos seja uma observação trivial, pode ser usado para demonstrar resultados possivelmente inesperados . Por exemplo, em toda 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 exatamente o mesmo número de fios de cabelo.
[editar] Generalizações do princípio da casa dos pombos
Uma versão generalizada desse princípio declara que, se "n" objetos distintos para ser alocados à "m" recipientes, então pelo menos um recipiente deve conter não menos que 
objetos, onde 
denota o menor inteiro igual ou superior a x.
Uma generalização probabilística do principio da casa do pombo 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
onde
é um fatorial decrescente. 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 à 4 casa de pombos, há uma chance de 25% que pelo menos uma casa de pombo terá mais que um pombo, para 5 pombos e 10 casas, a probabilidade é de 69,76%; e para 10 pombos para 20 casas a probabilidade é de 93,45%.
