Re: [obm-l] casa dos pombos....

["marcelo oliveira" <marcelo_rufino@xxxxxxxxxxx>]

>1)Numa sequencia de mn+1 reais distintos, existe ou uma sequencia crescente 
>de m+1 números ou uma sequencia descrescente de n+1 números.

>2) Prove que qualquer que seja a sequencia de n inteiros, é sempre possível 
>escolher um bloco de inteiros adjacentes cuja soma seja divsível por n.


Podemos separar os n inteiros (a1, a2, …, an) da seguinte forma:
a1
a1 + a2
a1 + a2 + a3
………………
a1 + a2 + … + an
Se um destes somatórios for divisível por n então acabou o problema.
Caso nenhum destes somatórios seja divisível por n, temos n – 1 restos da 
divisão por n que estes termos podem assumir.
Como temos n termos e n – 1 restos possíveis, teremos dois termos com mesmo 
resto quando dividido por n.
Subtraindo estes dois termos obteremos um termo que é divisível por n e da 
forma  aj + aj + 1 + … + an


>                        Crom
>=========================================================================

Até mais,
Marcelo Rufino de Oliveira


_________________________________________________________________
Chat with friends online, try MSN Messenger: http://messenger.msn.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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================