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

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

   Caro Domingos,
   O problema na recorrencia que voce mencionou e' que quando voce quiser
excluir as combinacoes que incluem o par (ki,kj) (ou contar as que somam
(ki,kj)) com k=p, deve levar em conta que (pi,pj)=(0,0). Isso complica as
coisas...
   Abracos,
            Gugu

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

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