[obm-l] Re: [obm-l] Re: [obm-l] Combinatoria

[yurigomes@xxxxxxxxxxxxxx]

 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: yurigomes@zipmail.com.br
>>Reply-To: obm-l@mat.puc-rio.br
>>To: obm-l@mat.puc-rio.br
>>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
=========================================================================