O principio da casa dos pombos (PCP), ou Principio de Dirichlet, na sua forma mais simples, diz que se vc tem n+1 bolas e quer distribuí-las em n gavetas, então algumas das gavetas deverá conter no minimo duas bolas.
Isso eh bem intuitivo. Para provar isso, suponha por absurdo que não. Então cada gaveta terá no máximo 1 bola. Como temos n gavetas, isso nos dá um numero maximo de 1+1+...+1= n bolas. Mas nós temos n+1 !! Absurdo. E o resultado segue. Outra forma do PCP é a seguinte: se agora vc tem nk+ 1 bolas e quer distribui-las em n gavetas, alguma das gavetas terá no minimo k+ 1 bolas. Veja que a versão anterior é um caso particular desta ultima, com k= 1. Tente prová-la, é a mesma idéia ( absurdo! ). Ateh mais, Yuri -- Mensagem original -- > >Alguem me explica como eh esse principio da casa dos pombos? > >obrigado > >>From: [EMAIL PROTECTED] >>Reply-To: [EMAIL PROTECTED] >>To: [EMAIL PROTECTED] >>Subject: [obm-l] Re: [obm-l] Combinatoria >>Date: Sat, 12 Jul 2003 12:22:50 -0300 >> >> >> Oi Marcio, >> Se eu não me engano, esse problema tem no Problem Solving: >> Seja x_i= número de partidas jogadas até o dia i, inclusive. >> Como o enxadrista joga no minimo 1 partida por dia e no máximo 11x12= >>132 no total, temos >> 1<= a_1< a_2<...< a_77<= 132. Some 20 na desigualdade: >> 21<= a_1 + 20<...< a_77 + 20 <= 152. >> Então, os números a_1, a_2,..., a_77, a_1 + 20,...,a_77 + 20 estão entre >>1 e 152. Como temos 154 números, pelo princípio da casa dos pombos existem >>dois deles iguais. Assim, existem dois indices i e j, i!=j, tais que >> a_i= a_j + 20. >> Ora, isso é equivalente ao enxadrista ter jogado exatamente vinte >>partidas >>entre os dias i+1 e j. >> >> Ateh mais, >> Yuri >> >>-- Mensagem original -- >> >> > Nao estou conseguindo fazer a seguinte questao, do livro de >>combinatoria >> >do Morgado: >> >Um enxadrista joga partidas de xadrez durante onze semanas consecutivas. >> >Sabe-se que ele sempre joga ao menos uma partida por dia, e jamais joga >>mais >> >de 12 partidas em uma semana. Mostre que existe um periodo de dias >>consecutivos >> >no qual ele joga exatamente 20 partidas. >> > Alguem tem alguma dica? >> > >> > Abracos, >> > Marcio >> > >> >>[]'s, Yuri >>ICQ: 64992515 >> >> >>------------------------------------------ >>Use o melhor sistema de busca da Internet >>Radar UOL - http://www.radaruol.com.br >> >> >> >>========================================================================= >>Instruções para entrar na lista, sair da lista e usar a lista em >>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >>========================================================================= > >_________________________________________________________________ >MSN Hotmail, o maior webmail do Brasil. http://www.hotmail.com > >========================================================================= >Instruções para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >========================================================================= > []'s, Yuri ICQ: 64992515 ------------------------------------------ Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================