Re: [obm-l] Casa de Pombos e Desigualdade com Pi

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi,

Primeiro, eu enviei sem querer um email antes do
último que mandei. Eu cliquei no botão errado,
desculpem-me.

Eu descobri que depois de provar para primo, é só
fazer com indução sobre a quantidade de fatores primos
(não necessariamente distintos) de n.

Seja n = pk, p primo. Separe 2k-1 dos 2pk-1 números.
Pela hipótese de indução, existem k cuja soma é
divisível por k. Tome os outros k-1 e coloque de
volta, obtendo 2(p-1)k-1 números. Separe novamente
2k-1 desses números e aplique a hipótese de indução
mais uma vez. Na verdade, aplique a hipótese de
indução 2p-1 vezes, obtendo 2p-1 conjuntos disjuntos
dois a dois de k números, todos eles com somas
divisíveis por k. Cosidere agora as 2p-1 somas
obtidas, todas múltiplas de k. Se k tem m fatores p,
divida todas as somas por p^m. Aplique agora a
hipótese de indução sobre esses 2p-1 números: p dessas
somas (divididas por p^m) somam um múltiplo de p. Aí
acabou, pois a soma original é múltipla de p^(m+1)
(conseguimos colocar mais um fator p) e, portanto, de
n. E temos p*k = n números.

Muito legal esse problema. Tem um outro muito bom
também, que é o teorema de Cauchy-Davenport:

Seja p um número primo e A, B subconjuntos de Z/pZ. Se
A + B := {a+b,a em A e b em B} e |X| é a quantidade de
elementos do conjunto X, prove que
    |A + B| >= mín(|A| + |B| - 1, p).

[]'s
Shine

--- "claudio.buffara" <claudio.buffara@terra.com.br>
wrote:

> Esse tah me enchendo o saco:
> 
> Prove que toda sequencia de 2n-1 inteiros (nao
> necessariamente distintos) possui uma subsequencia
> de n inteiros cuja soma eh divisivel por n.
> 
> ***
> 
> Ha alguns meses alguem mandou pra lista o problema
> de se provar que:
> raiz(2) + raiz(3) > Pi.
> Foi enviada alguma solucao?
> 
> []s,
> Claudio.
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.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
=========================================================================