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

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Sat, Apr 13, 2002 at 07:45:45PM -0400, DEOLIVEIRASOU@aol.com wrote:
> Alguem poderia resolver esses??
> 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.

Estes dois problemas são exemplos clássicos do princípio da casa de pombo.

No primeiro, para cada real da seqüência, associe um par de inteiros
positivos: o primeiro inteiro é o tamanho da maior seqüência crescente
começando ali e o segundo inteiro é o tamanho da maior seqüência decrescente
acabando ali. Supondo por absurdo que a conclusão seja falsa, a primeira
coordenada é sempre <= m e a segunda sempre <= n. Como temos mn+1 pares,
há dois pares iguais, digamos associados a xa e xb com a < b, sendo este par
(i,j). Se  xa < xb podemos obter uma seqüência crescente de tamanho i+1
começando em xa, basta tomar xa e depois uma seq de tamanho i começando em xb.
Por outro lado se xa > xb podemos obter uma seq decrescente de tamanho j+1
acabando em xb, basta tomar uma de tamanho j acabando em xa e acrescentar xb
no final. Em qualquer um dos dois casos temos um absurdo.

No segundo, considere os valores módulo n dos n+1 blocos começando no início
da seqüência (inclusive o bloco vazio e a seqüência inteira). Dois destes
blocos têm o mesmo valor módulo n logo a diferença é um múltiplo de n.

[]s, N.
=========================================================================
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>
=========================================================================