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

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

O de casa dos pombos é bem legal, na verdade.

Por enquanto eu sei provar para n primo. Por motivos
psicológicos, seja n = p :).

Considere todas as somas possíveis com p números. Se
nenhuma delas é divisível por p então cada soma
elevada a p-1 é 1 mód p. Some todas essas somas
elevadas a p-1.

Vamos abrir essa soma de somas. Vamos ver o caso p = 3
para entender melhor a idéia e depois generalizar.
Sendo, então, x,y,z,w,t os números, abrimos, módulo 3,
a soma
  (x+y+z)^2 + (x+y+w)^2 + (x+y+t)^2 + (x+z+w)^2
+ (x+z+t)^2 + (x+w+t)^2 + (y+z+w)^2 + (y+z+t)^2
+ (y+w+t)^2 + (z+w+t)^2

Se ninguém é divisível por 3, todo mundo é 1 módulo 3
e obtemos 10. Mas x^2, por exemplo, aparece 6 vezes
(combinatoriamente: em binom(4,2) caras, pois basta
escolher os dois "companheiros" a e b de x em
(x+a+b)^2), e 2xy, em 3 caras (binom(3,1) - você pode
conluir por quê?). Então a soma total é 0 módulo 3,
absurdo. Logo uma das somas é divisível por 3.

Agora, o caso geral (para primo). Na soma, cada
x_1^a_1x_2^a_2...x_k^a_k aparece nas somas que contêm
x_1,x_2,...,x_k, que são em total de binom(2p-1-k,p-k)
= binom(2p-1-k,p-1) (basta escolhermos os demais p-k
números entre os 2p-1-k números restantes). Note que 1
<= k <= p-1, pois a_1 + a_2 + ... + a_k = p-1, já que
cada soma está sendo elevada a p-1. Mas
binom(2p-1-k,p-1) = produto de p-1 consecutivos/(p-1)!
sendo que nesse produto é obrigatório aparecer um
múltiplo de p, pois 2p-1-k = p-1-k (mód p) e 0 <=
p-1-k <= p-2. Logo cada termo aparece multiplicado por
um múltiplo de p e logo a soma de somas elevadas a p-1
é zero. Se nenhuma das somas é divisível por p, então
a soma das somas elevadas a p-1 é igual a
binom(2p-1,p) módulo p. Mas acontece que (2p-1)! tem
um único fator p, que é cortado pelo p! no binomial.
Ou seja, binom(2p-1,p) não é divisível por p, absurdo.

Logo uma das somas é múltipla de p.

Para n composto ainda não sei fazer, mas eu li que dá
para reduzir esse caso para n primo.

[]'s
Shine

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