Princípio da casa dos pombos: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: eu:Usategi printzipio; mudanças triviais |
|||
Linha 1:
[[
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 [[elemento]]s de um [[conjunto]] [[finito]] A
É também conhecido como '''teorema de Dirichlet'' ou ''princípio das gavetas de Dirichlet''', pois supõe-se que o primeiro relato deste principio foi feito por [[Dirichlet]] em [[1834]], com o nome de ''Schubfachprinzip'' ("princípio das gavetas").
Linha 8:
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 se ter certeza que haverá pelo menos duas delas façam aniversário no mesmo mês?
'''Resposta:''' 13 pessoas.
Linha 20:
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
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]]:
Linha 27:
:<math>1 - \frac{m!}{(m-n)!\;m^n} = 1 - \frac{m^{\underline{n}}}{m^n}, \!</math>
onde <math>m^{\underline{n}}</math> é 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''),
== Ligações externas ==
*{{en}} [http://www.cut-the-knot.org/do_you_know/pigeon.shtml Princípio do pombal] na página ''cut-the-knot''
*{{en}} [http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html "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]]
Linha 53:
[[en:Pigeonhole principle]]
[[es:Principio del palomar]]
[[eu:Usategi printzipio]]
[[fa:اصل لانه کبوتری]]
[[fi:Kyyhkyslakkaperiaate]]
| |||