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
=========================================================================