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

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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

Boa! Até que não é complicado...

>     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

Entendo... realmente, a parte difícil fica determinar T(0, 0) sabendo apenas
que os outros valores são todos iguais... Mas vou tentar mais um pouco, quem
sabe tem uma maneira simples.

Pensei em montar algo do tipo, t0, t1, t2, ... t[i] == número de combinações
de i elementos com soma sendo um par qualquer que não (0, 0)...
e q0, q1, ... q[i] sendo o número de combinações de i elementos com soma (0,
0).

considere todas as combinações de n elementos resultando em (i, j)
para obter (0, 0) podemos simplesmente inserir o elemento (-i, -j) nessa
combinação... o problema é que esse elemento pode já estar lá dentro!

vamos tentar contar quantas combinações incluem (-i, -j)
fixamos o (-i, -j) e sobram n-1 elementos livres que não sejam o mesmo par e
cuja soma seja (2i, 2j)...
estou percebendo que tem uma certa recorrência nessa afirmação!

t[n-1] - (t[n-2] - (t[n-3] - ... ))

acho que fica algo como:
q[n+1] = (p²- 1) * (t[n] - t[n-1] + t[n-2] - t[n-3] + ...)

será que isso está certo?

queremos obter T(0, 0) = somatório{ i = 0..p² } q[i]
sabendo que
T(0, 0) + (p² - 1)*(t0 + t1 + t2 + ... + t[p²]) = 2^(p²)


[ ]'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
=========================================================================