Princípio de buraco de pombo - Pigeonhole principle
Em matemática , o princípio do escaninho afirma que se os itens são colocados em contêineres, com , então, pelo menos um contêiner deve conter mais de um item. Por exemplo, se um tem três luvas (e nenhuma é ambidestro / reversível), então deve haver pelo menos duas luvas destras, ou pelo menos duas luvas canhotas, porque há três objetos, mas apenas duas categorias de destreza para colocá-los. Esta declaração aparentemente óbvia, um tipo de argumento de contagem , pode ser usada para demonstrar resultados possivelmente inesperados. Por exemplo, dado que a população de Londres é maior do que o número máximo de fios de cabelo que pode estar presente na cabeça de um ser humano, o princípio do escaninho exige que haja pelo menos duas pessoas em Londres com o mesmo número de fios de cabelo em seus cabeças.
Embora o princípio do escaninho apareça já em 1624 em um livro atribuído a Jean Leurechon , é comumente chamado de princípio da caixa de Dirichlet ou princípio da gaveta de Dirichlet após um tratamento de 1834 do princípio por Peter Gustav Lejeune Dirichlet sob o nome de Schubfachprinzip ("princípio da gaveta" ou "princípio de prateleira").
O princípio tem várias generalizações e pode ser declarado de várias maneiras. Em uma versão mais quantificada: para números naturais e , se os objetos são distribuídos entre conjuntos, o princípio do escaninho afirma que pelo menos um dos conjuntos conterá pelo menos objetos. Para arbitrário e isso generaliza para onde e denotam as funções de piso e teto , respectivamente.
Embora a aplicação mais direta seja para conjuntos finitos (como pombos e caixas), ele também é usado com conjuntos infinitos que não podem ser colocados em correspondência um a um . Para fazer isso, é necessária a declaração formal do princípio do escaninho, que é "não existe uma função injetiva cujo codomínio seja menor que seu domínio " . Provas matemáticas avançadas, como o lema de Siegel, se baseiam nesse conceito mais geral.
Etimologia
Dirichlet publicou suas obras em francês e alemão, usando o Schubfach alemão ou o tiroir francês . O significado original estrito destes termos corresponde à gaveta inglesa , ou seja, uma caixa com a tampa aberta que pode ser introduzida e retirada do armário que a contém . (Dirichlet escreveu sobre a distribuição de pérolas entre gavetas.) Esses termos foram transformados na palavra escaninho no sentido de um pequeno espaço aberto em uma escrivaninha, armário ou parede para guardar cartas ou papéis , metaforicamente enraizado em estruturas que abrigam pombos.
Como os móveis com escaninhos são comumente usados para armazenar ou classificar coisas em muitas categorias (como cartas em uma agência dos correios ou chaves de quartos em um hotel), o escaninho de tradução pode ser uma representação melhor da metáfora da gaveta original de Dirichlet. Essa compreensão do termo escaninho , referindo-se a algumas características de móveis, está desaparecendo - especialmente entre aqueles que não falam inglês nativamente, mas como uma língua franca no mundo científico - em favor de uma interpretação mais pictórica, envolvendo literalmente pombos e buracos. A interpretação sugestiva (embora não enganosa) de "escaninho" como "pombal" encontrou recentemente seu caminho de volta a uma retrotradução alemã do "princípio do escaninho" como "Taubenschlagprinzip".
Além dos termos originais "Schubfachprinzip" em alemão e "Principe des tiroirs" em francês, outras traduções literais ainda estão em uso em búlgaro ("принцип на чекмеджетата"), chinês ("抽屉 原理"), dinamarquês ("Skuffeprincippet"), Holandês ("ladenprincipe"), húngaro ("skatulyaelv"), italiano ("principio dei cassetti"), japonês ("引 き 出 し 論 法"), persa ("اصل لانه کبوتری"), polonês ("zasada szufladkowa"), sueco ( "Lådprincipen"), turco ("çekmece ilkesi") e vietnamita ("nguyên lý hộp").
Exemplos
Pegando meia
Suponha que uma gaveta contenha uma mistura de meias pretas e azuis, cada uma das quais pode ser usada em qualquer um dos pés, e que você está puxando várias meias da gaveta sem olhar. Qual é o número mínimo de meias puxadas necessárias para garantir um par da mesma cor? Usando o princípio do escaninho, para ter pelo menos um par da mesma cor ( m = 2 furos, um por cor) usando um escaninho por cor, você precisa puxar apenas três meias da gaveta ( n = 3 itens). Ou você tem três de uma cor, ou você tem dois de uma cor e um da outra.
Aperto de mãos
Se houver n pessoas que podem apertar a mão umas das outras (onde n > 1 ), o princípio da classificação mostra que sempre há um par de pessoas que aperta a mão do mesmo número de pessoas. Nesta aplicação do princípio, o 'buraco' ao qual uma pessoa é atribuída é o número de mãos apertadas por essa pessoa. Como cada pessoa aperta a mão de um certo número de pessoas de 0 a n - 1 , há n buracos possíveis. Por outro lado, o orifício '0' ou o orifício ' n - 1' ou ambos devem estar vazios, pois é impossível (se n > 1 ) para alguma pessoa apertar a mão de todo mundo enquanto outra pessoa aperta a mão de ninguém. Isso deixa n pessoas para serem colocadas em no máximo n - 1 orifícios não vazios, para que o princípio se aplique.
Este exemplo de aperto de mão é equivalente à afirmação de que em qualquer gráfico com mais de um vértice , há pelo menos um par de vértices que compartilham o mesmo grau . Isso pode ser visto associando cada pessoa a um vértice e cada aresta a um aperto de mão.
Contagem de cabelo
Pode-se demonstrar que deve haver pelo menos duas pessoas em Londres com o mesmo número de cabelos na cabeça como segue. Como uma cabeça humana típica tem uma média de cerca de 150.000 fios de cabelo, é razoável supor (como um limite superior) que ninguém tem mais de 1.000.000 de fios de cabelo na cabeça ( m = 1 milhão de orifícios). Existem mais de 1.000.000 de pessoas em Londres ( n é maior que 1 milhão de itens). Atribuindo um escaninho para cada número de fios de cabelo na cabeça de uma pessoa, e atribuindo pessoas aos escaninhos de acordo com o número de fios de cabelo em sua cabeça, deve haver pelo menos duas pessoas atribuídas ao mesmo escaninho pela 1.000.001ª atribuição (porque eles têm o mesmo número de fios de cabelo em suas cabeças) (ou, n > m ). Supondo que Londres tenha 8,9 milhões de habitantes, pode-se até afirmar que pelo menos nove londrinos têm o mesmo número de cabelos, pois ter oito londrinos em cada um dos 1 milhão de escaninhos corresponde a apenas 8 milhões de pessoas.
Para o caso médio ( m = 150.000 ) com a restrição: menor número de sobreposições, haverá no máximo uma pessoa atribuída a cada escaninho e a 150.001ª pessoa atribuída ao mesmo escaninho que outra pessoa. Na ausência dessa restrição, pode haver escaninhos vazios porque a "colisão" ocorre antes da 150.001ª pessoa. O princípio apenas prova a existência de uma sobreposição; não diz nada sobre o número de sobreposições (que se enquadra no assunto da distribuição de probabilidade ).
Há uma alusão passageira, satírica em inglês a esta versão do princípio em A History of the Athenian Society , prefixada a "Um suplemento ao oráculo ateniense: sendo uma coleção das perguntas e respostas restantes nos antigos mercúrios atenienses", (Impresso por Andrew Bell, Londres, 1710). Parece que a questão de saber se havia duas pessoas no mundo que têm o mesmo número de cabelos na cabeça? foi criado no Mercúrio Ateniense antes de 1704.
Talvez a primeira referência escrita ao princípio do escaninho apareça em 1622 em uma frase curta da obra latina Selectæ Propositiones , do jesuíta francês Jean Leurechon , onde ele escreveu "É necessário que dois homens tenham o mesmo número de cabelos, écus, ou outras coisas, como cada um. " O princípio completo foi explicado dois anos depois, com exemplos adicionais, em outro livro que muitas vezes foi atribuído a Leurechon, mas pode ter sido escrito por um de seus alunos.
O problema do aniversário
O problema do aniversário pergunta, para um conjunto de n pessoas escolhidas aleatoriamente, qual é a probabilidade de que algum par faça aniversário no mesmo dia? O problema em si está preocupado principalmente com probabilidades contra-intuitivas; no entanto, também podemos dizer pelo princípio do escaninho que, se houver 367 pessoas na sala, há pelo menos um par de pessoas que compartilham o mesmo aniversário com 100% de probabilidade, pois há apenas 366 aniversários possíveis para escolher ( incluindo 29 de fevereiro, se houver).
Torneio de equipe
Imagine sete pessoas que querem jogar em um torneio de times ( n = 7 itens), com uma limitação de apenas quatro times ( m = 4 buracos) para escolher. O princípio do escaninho nos diz que nem todos podem jogar em times diferentes; deve haver pelo menos uma equipe com pelo menos dois dos sete jogadores:
Subconjunto soma
Qualquer subconjunto de tamanho seis do conjunto S = {1,2,3, ..., 9} deve conter dois elementos cuja soma seja 10. Os escaninhos serão rotulados pelos dois subconjuntos de elementos {1,9}, {2 , 8}, {3,7}, {4,6} e o singleton {5}, cinco escaninhos ao todo. Quando os seis "pombos" (elementos do subconjunto de tamanho seis) são colocados nesses escaninhos, cada pombo indo para o escaninho que o contém em seu rótulo, pelo menos um dos escaninhos rotulados com um subconjunto de dois elementos terá dois pombos nele.
Usos e aplicações
O princípio pode ser usado para provar que qualquer algoritmo de compressão sem perdas , desde que torne algumas entradas menores (como o nome sugere compressão), também tornará algumas outras entradas maiores. Caso contrário, o conjunto de todas as sequências de entrada até um determinado comprimento L poderia ser mapeado para o conjunto (muito) menor de todas as sequências de comprimento menor do que L sem colisões (porque a compressão é sem perdas), uma possibilidade que o princípio do escaninho exclui.
Um problema notável na análise matemática é, para um número irracional fixo a , mostrar que o conjunto {[ na ]: n é um inteiro} de partes fracionárias é denso em [0, 1]. Descobrimos que não é fácil encontrar explicitamente inteiros n , m tais que | na - m | < e , onde e > 0 é um pequeno número positivo e a é algum número irracional arbitrário. Mas se tomarmos M tal que 1 / M < e , pelo princípio do escaninho deve haver n 1 , n 2 ∈ {1, 2, ..., M + 1 } tal que n 1 a e n 2 a estão em a mesma subdivisão de inteiro de tamanho 1 / M (há apenas M dessas subdivisões entre inteiros consecutivos). Em particular, pode-se encontrar n 1 , n 2 de modo que n 1 a esteja em ( p + k / M , p + ( k + 1) / M ) e n 2 a esteja em ( q + k / M , q + ( k + 1) / M ) , para alguns p , q inteiros ek em {0, 1, ..., M - 1 }. Pode-se então verificar facilmente que ( n 2 - n 1 ) a está em ( q - p - 1 / M , q - p + 1 / M ) . Isso implica que [ na ] <1 / M < e , onde n = n 2 - n 1 ou n = n 1 - n 2 . Isso mostra que 0 é um ponto limite de {[ na ]}. Pode-se então usar esse fato para provar o caso para p em (0, 1] : encontre n tal que [ na ] <1 / M < e ; então, se p ∈ (0, 1 / M ], a prova está completa. Caso contrário, p ∈ ( j / M , ( j + 1) / M ], e definindo k = sup { r ∈ N : r [ na ] < j / M }, obtém-se | [( k + 1) na ] - p | <1 / M < e .
As variantes ocorrem em várias provas. Na prova do lema do bombeamento para linguagens regulares , uma versão que mistura conjuntos finitos e infinitos é usada: Se infinitos objetos são colocados em caixas finitas, então existem dois objetos que compartilham uma caixa. Na solução de Fisk para o problema da galeria de arte, uma espécie de inverso é usada: se n objetos são colocados em k caixas, então há uma caixa contendo no máximo n / k objetos.
Formulações alternativas
O que se segue são formulações alternativas do princípio do escaninho.
- Se n objetos são distribuídos em m lugares, e se n > m , então algum lugar recebe pelo menos dois objetos.
- (formulação equivalente de 1) Se n objetos são distribuídos em n lugares de tal forma que nenhum lugar recebe mais de um objeto, então cada lugar recebe exatamente um objeto.
- Se n objetos são distribuídos em m lugares, e se n < m , então algum lugar não recebe nenhum objeto.
- (formulação equivalente de 3) Se n objetos são distribuídos em n lugares de tal forma que nenhum lugar recebe nenhum objeto, então cada lugar recebe exatamente um objeto.
Forma forte
Sejam q 1 , q 2 , ..., q n inteiros positivos. Se
objectos são distribuídos em n caixas, em seguida, tanto a primeira caixa contém, pelo menos, q 1 objectos, ou a segunda caixa contém, pelo menos, q 2 objectos, ..., ou o n caixa th contém, pelo menos, q n objectos.
A forma simples é obtida tomando q 1 = q 2 = ... = q n = 2 , o que dá n + 1 objetos. Tomando q 1 = q 2 = ... = q n = r dá a versão mais quantificada do princípio, a saber:
Sejam n e r inteiros positivos. Se n ( r - 1) + 1 objetos são distribuídos em n caixas, então pelo menos uma das caixas contém r ou mais dos objetos.
Isso também pode ser declarado como, se k objetos discretos forem alocados para n contêineres, então pelo menos um contêiner deve conter pelo menos objetos, onde é a função de teto , denotando o menor inteiro maior ou igual a x . Da mesma forma, pelo menos um contêiner deve conter não mais do que objetos, onde é a função piso , denotando o maior inteiro menor ou igual a x .
Generalizações do princípio do escaninho
Uma generalização probabilística do princípio do escaninho afirma que se n pombos forem colocados aleatoriamente em m escaninhos com probabilidade uniforme 1 / m , então pelo menos um escaninho terá mais de um pombo com probabilidade
onde ( m ) n é o fatorial decrescente m ( m - 1) ( m - 2) ... ( m - n + 1) . Para n = 0 e para n = 1 (e m > 0 ), essa probabilidade é zero; em outras palavras, se houver apenas um pombo, não pode haver conflito. Para n > m (mais pombos do que escaninhos), é um, caso em que coincide com o princípio do escaninho comum. Mas mesmo que o número de pombos não exceda o número de escaninhos ( n ≤ m ), devido à natureza aleatória da atribuição dos pombos aos escaninhos, muitas vezes há uma chance substancial de que ocorram confrontos. Por exemplo, se 2 pombos são atribuídos aleatoriamente a 4 escaninhos, há 25% de chance de que pelo menos um escaninho tenha mais de um pombo; para 5 pombos e 10 buracos, essa probabilidade é de 69,76%; e para 10 pombos e 20 buracos é cerca de 93,45%. Se o número de buracos permanecer fixo, sempre haverá uma probabilidade maior de um par quando você adicionar mais pombos. Esse problema é tratado com muito mais detalhes no paradoxo do aniversário .
Uma outra generalização probabilística é que quando uma variável aleatória de valor real X tem uma média finita E ( X ) , então a probabilidade é diferente de zero que X é maior ou igual a E ( X ) , e da mesma forma a probabilidade é diferente de zero que X é menor ou igual a E ( X ) . Para ver que isso implica o princípio de escaninho padrão, pegue qualquer arranjo fixo de n pombos em m buracos e seja X o número de pombos em um buraco escolhido uniformemente ao acaso. A média de X é n / m , portanto, se houver mais pombos do que buracos, a média é maior que um. Portanto, às vezes X é pelo menos 2.
Conjuntos infinitos
O princípio de pombo pode ser estendido para conjuntos infinitos por fraseado em termos de números cardinais : se a cardinalidade do conjunto A é maior do que a cardinalidade do conjunto B , então não há injecção de um de B . No entanto, nesta forma, o princípio é tautológica , uma vez que o significado da afirmação de que a cardinalidade do conjunto A é maior do que a cardinalidade do conjunto B é exatamente o que não há mapa injective de A para B . No entanto, adicionar pelo menos um elemento a um conjunto finito é suficiente para garantir que a cardinalidade aumente.
Outra maneira de expressar o princípio do escaninho para conjuntos finitos é semelhante ao princípio de que conjuntos finitos são Dedekind finitos : sejam A e B conjuntos finitos. Se houver uma injeção de A para B que não seja injetiva, nenhuma injeção de A para B será injetável. Na verdade, nenhuma função de qualquer tipo de A a B é injetiva. Isso não é verdade para conjuntos infinitos: considere a função nos números naturais que envia 1 e 2 para 1, 3 e 4 para 2, 5 e 6 para 3 e assim por diante.
Há um princípio semelhante para conjuntos infinitos: se incontáveis muitos pombos são enfiados em numerosos escaninhos, existirá pelo menos um escaninho com incontáveis muitos pombos enfiados nele.
No entanto, este princípio não é uma generalização do princípio do escaninho para conjuntos finitos: em geral, é falso para conjuntos finitos. Em termos técnicos que diz que, se A e B são conjuntos finitos tais que qualquer função surjective de A para B não é injetora, então existe um elemento b de B tal que existe uma bijeção entre o preimage de b e A . Esta é uma afirmação bastante diferente e é absurda para grandes cardinalidades finitas.
Mecânica quântica
Yakir Aharonov et al. apresentaram argumentos de que o princípio do escaninho pode ser violado na mecânica quântica e propuseram experimentos interferométricos para testar o princípio do escaninho na mecânica quântica. No entanto, pesquisas posteriores questionaram essa conclusão. Em uma pré-impressão do arXiv de janeiro de 2015, os pesquisadores Alastair Rae e Ted Forgan, da Universidade de Birmingham, realizaram uma análise teórica da função de onda , empregando o princípio de escaninho padrão, no voo de elétrons em várias energias por meio de um interferômetro . Se os elétrons não tivessem nenhuma força de interação, cada um deles produziria um único pico perfeitamente circular. Em alta força de interação, cada elétron produz quatro picos distintos para um total de 12 picos no detector; esses picos são o resultado das quatro possíveis interações que cada elétron pode experimentar (sozinho, junto com a primeira outra partícula apenas, juntamente com a segunda outra partícula apenas, ou todas as três juntas). Se a força de interação fosse bastante baixa, como seria o caso em muitos experimentos reais, o desvio de um padrão de interação zero seria quase indiscernível, muito menor do que o espaçamento da rede de átomos em sólidos, como os detectores usados para observá-los padrões. Isso tornaria muito difícil ou mesmo impossível distinguir uma força de interação fraca, mas diferente de zero, de nenhuma interação, e assim dar uma ilusão de três elétrons que não interagiram apesar de todos os três passarem por dois caminhos.
Veja também
- Axioma de escolha
- Teorema de Blichfeldt
- Princípios Combinatórios
- Prova Combinatória
- Conjunto infinito Dedekind
- O paradoxo de Hilbert do Grand Hotel
- Teorema Multinomial
- Teorema de Ramsey
- Símbolo Pochhammer
Notas
Referências
- Brualdi, Richard A. (2010), Introductory Combinatorics (5ª ed.), Pentice Hall, ISBN 978-0-13-602040-0
- Fletcher, Peter; Patty, C.Wayne (1987), Foundations of Higher Mathematics , PWS-Kent, ISBN 978-0-87150-164-6
- Grimaldi, Ralph P. (1994), Discrete and Combinatorial Mathematics: An Applied Introduction (3rd ed.), Addison-Wesley, ISBN 978-0-201-54983-6
- Herstein, IN (1964), Topics In Algebra , Waltham: Blaisdell Publishing Company, ISBN 978-1114541016
links externos
- "Princípio da caixa de Dirichlet" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
- " O estranho caso do princípio do buraco do pombo "; Edsger Dijkstra investiga interpretações e reformulações do princípio.
- " O princípio do buraco do pombo "; Exemplos elementares do princípio em uso por Larry Cusick.
- " Princípio do Pigeonhole da Miscelânea e dos Puzzles da Matemática Interativa "; Análise básica do Princípio de Buraco de Pombo e exemplos por Alexander Bogomolny .
- " 16 aplicações divertidas do princípio do escaninho "; Fatos interessantes derivados do princípio.
- "Quantos humanos têm o mesmo número de pelos do corpo?" . Série PBS Infinite . 1 ° de dezembro de 2016 - via YouTube .