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