Pular para o conteúdo principal

O princípio da casa dos pombos

Assista ao vídeo.


Como o cara aí de cima falou :D , os problemas de análise combinatória podem ser divididos em dois tipos: os de contagem e os de existência. Os de contagem utilizam as nossas ferramentas conhecidas, como a Combinação, a Permutação e o Arranjo e permitem-nos contar de quantas maneiras podemos organizar uma estante de livros, quantos anagramas possui uma palavra, como podemos estacionar um carro em um estacionamento, entre outros. Já os problemas de existência utilizam uma ferramenta simples, porém poderosa: o Princípio da Casa dos Pombos.



É interessante notar que esse princípio era chamado originalmente de Princípio da Gaiola dos Pombos, mas como esse nome foi considerado politicamente incorreto, o nome dele foi mudado. Ele também pode ser chamado de Princípio das Gavetas de Dirichlet.


O que esse princípio afirma é extremamente simples: se colocarmos n+1 pombos em n gaiolas, então pelo menos uma gaiola deverá conter 2 ou mais pombos. A demonstração é extremamente óbvia, pois se distribuirmos apenas um pombo por gaiola, no final teremos colocado epenas n pombos, o que contradiz a hipótese inicial.


Esse princípio nos permite fazer considerações interessantes como por exemplo: se em uma festa de aniversário infantil estiverem presentes 8 crianças, podemos afirmar com certeza que pelo menos duas delas nasceram no mesmo dia da semana (afinal, temos apenas 7 dias na semana); Se em um processo de seleção tivermos 366 candidatos, certamente no mínimo dois fazem aniversário no mesmo dia (lembre-se que o ano tem 365 dias e que as pessoas que nascem em 29 de Fevereiro são registradas como se tivessem nascido no dia 28 ou primeiro de Março). Basta enxergar as pessoas como pombos e os dias como casas.


Há, ainda, uma segunda versão do princípio a qual nos permite generalizá-lo para qualquer número de pombos: ela afirma que se n gaiolas são ocupadas por nk + 1 pombos, então pelo menos uma gaiola deverá conter pelo menos k + 1 pombos. A demonstração é extremamente similar à primeira.


Se considerarmos n gaiolas e k pombos, podemos utilizar a fórmula [k-1/n]+1 para calcular o mínimo de pombos que uma gaiola deverá conter, onde k é o número de pombos e n o de gaiolas. O colchete aberto em cima representa o menor inteiro, ou seja, um arredondamento para baixo.


Por exemplo: para descobrirmos quantas pessoas nasceram no mesmo dia da semana em um grupo de 20 indivíduos, basta fazer a conta Exemplo de problema envolvendo o PCP.


Outro exemplo bem interessante é o que nos permite provar que um determinado número divide outros infinitos números de uma determinada forma. Por exemplo: vamos provar que 11 divide infinitos números da forma 363636... Para isso, vamos escrever a seguinte lista:




36


3636


363636


...


363636363636363636363636



Como você pode perceber, nós temos 12 números da forma 36...36 (pombos) para apenas 11 classes de congruência (gaiolas). Assim, pelo Princípio da Casa dos Pombos, é óbvio que dois desses números estão na mesma classe de congruência, ou seja, deixam o mesmo resto na divisão por 11.


Sejam estes números x = 36...36 e y = 36...36, com x > y. x - y é múltiplo de 11, mas também x - y = 36...360...0, ou seja, x - y = 36...36 x 10^k.


Ora, 11 divide 36...36 x 10^k, mas 11 não divide 10^k, logo podemos concluir que 11 divide 36...36, conforme queríamos demonstrar.


É importante salientar que esse tipo de problema só funciona se o número que divide não for múltiplo de 2 e/ou de 5 pois, se for, ele acabará dividindo 1o^k.

Comentários

  1. Excelente artigo..
    Me ajudou muuuuito!
    PERFEITO PRA CONCURSO.

    ResponderExcluir
  2. A figura CasaDosPombos2 está errada. o k deve ser igua a 20 e não a 10. Foi um engano, porque o resto da equação está certo.

    ResponderExcluir
  3. Obrigado! Vou corrigir assim que possível.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.