Re: [obm-l] Crianças e doces roubados

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Caro Domingos,
   Eu acho que ha' um problema na sua solucao: voce conta os subconjuntos de
Z/pZ x Z/pZ cujo numero de elementos nao e' multiplo de p e divide por
p^2-1, mas o numero de elementos dos conjuntos nao tem a ver com o problema,
e sim a soma dos elementos do conjunto. Voce pode notar que sua resposta ja'
nao esta' certa para p=2 nem para p=3. Por outro lado seu argumento que
mostra que os T(i,j) para (i,j) diferente de (0,0) sao todos iguais esta'
certo, e permite calcular esses T(i,j) em funcao de T(0,0):
T(i,j)=(2^(p^2)-T(0,0))/(p^2-1), se (i,j) nao e' (0,0).
   A resposta correta e' 4, para p=2 e ((p^2-1).2^p+2^(p^2))/p^2, para p>=3.
A solucao que eu fiz na prova foi a seguinte: Considere
f(x,y)=produto(1<=i,j<=p)(1+x^i.y^j). Podemos associar a cada subconjunto de
Z/pZ x Z/pZ um termo no desenvolvimento desse produto, e estamos
interessados nos termos nos quais os expoentes (depois de multiplicar) de x
e de y sao ambos multiplos de p. Para contar o numero desses termos, fazemos
o seguinte: sendo w=e^(2.Pi.i/p) uma raiz p-esima da unidade, somamos
f(w^r,w^s) com r e s variando entre 1 e p. Isso mata todos os termos do tipo
x^a.y^b onde a ou b nao e' multiplo de p, e os termos onde a e b sao
multiplos de p sao contados p^2 vezes. Essa soma e' 
Soma(1<=r,s<=p)(Produto(1<=i,j<=p)(1+w^(ri+sj))). 
   Se (r,s) nao e' igual a (p,p), quando i e j variam entre 1 e p, ri+sj
assume cada valor (modulo p) p vezes, donde
Produto(1<=i,j<=p)(1+w^(ri+sj))=(Produto(1<=k<=p)(1+w^k))^p=
=(-1)^p^2.(Produto(1<=k<=p)(-1-w^k))^p=(-1)^p^2.((-1)^p-1)^p (pois
x^p-1=Produto(x-w^k)), que e' 0 se p=2 e 2^p se p>=3. Por outro lado, se 
(r,s)=(p,p), nosso produto e' 2^(p^2).
Assim, nossa soma, que e' p^2 vezes o resultado que queremos, vale
2^(p^2)=16, se p=2 e (p^2-1).2^p+2^(p^2), se p>=3, o que prova a nossa
afirmacao.
   Abracos,
            Gugu 

>
>Aqui vai a minha solução para o problema:
>
>http://www.linux.ime.usp.br/~domingos/doces.ps
>http://www.linux.ime.usp.br/~domingos/doces.pdf
>
>Acho que o Postscript está mais legível...
>
>[ ]'s
>
>=========================================================================
>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>
>=========================================================================

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