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

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

   Caro Domingos, 
   Voce tem razao sobre nao ser obvio que T(i,0)=T(i,j) se i e j nao sao 0,
mas eu fiz as contas com a mesma tecnica da minha solucao e parece que
realmente sao iguais. Depois disso eu acho que arrumei um argumento mais
elementar. Por exemplo, para provar que T(1,0)=T(1,1),
podemos considerar a transformacao f(x,y)=(x,x+y). Assim, se temos um
conjunto de pontos (x,y) com soma (1,0), os pontos (x,x+y) terao soma
(1,1+0)=(1,1). Como f e' uma bijecao eu acho que isso termina a prova.
    Quanto a sua solucao inicial, eu nao tinha feito objecao a parte da
bijecao (que de fato, como voce observou depois, estava incompleta). Minha
objecao era quanto os C(p^2,kp) que apareciam, que davam a impressao de voce
estar preocupado com o tamanho dos conjuntos no lugar da soma dos seus
elementos. Por outro lado eu nao sei completar a solucao mesmo sabendo que T
so' pode assumir 2 valores: T(0,0) e os outros, e de fato eu nao sei fazer
sem usar algum truque como o da minha solucao, `a la funcoes geratrizes ou
coisa parecida.
    Abracos,
             Gugu

>
>>    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.
>
>não é bem isso que eu fiz....
>eu mostro simplesmente uma bijeção de conjuntos de elementos com n elementos
>com n != 0 mod p, com soma (i, j) e conjuntos de n elementos com soma (k,
>l)...
>
> 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).
>
>eu acho que descartando o meu erro no final --- onde considero todo conjunto
>de p elementos com soma (0, 0), sei lá o que aconteceu na hora de resolver o
>problema, acho que me confundi com o fato da característica de Zp ser p e
>acabei escrevendo besteira --- falta ainda provar que T(i, 0) = T(k, l) para
>quaisquer elementos i, k, l não nulos...
>
>>    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
>
>Legal!!! MUITO BOA...
>
>Agora me ajude a arrumar a minha solução, falta pouco... ignore o ps/pdf da
>página e veja a mensagem que mandei para o Johann, "Re: [obm-l] Como se faz
>um PS como esse?"...
>
>btw, acabei de notar um erro idiota nessa outra mensagem, onde está:
>"...todo elemento nulo tem inversa..."
>é evidente que deveria estar:
>"...todo elemento NÃO-nulo tem inversa..."
>
>[ ]'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
>=========================================================================

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