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

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

>    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

A idéia era mais ou menos essa:
Sabe-se que para todo par (i, j) != (0, 0) temos que o número de combinações
de n crianças cuja soma dos doces seja (i, j) é igual.
Toda combinação de n elementos cuja soma seja um par (i, j) != (0,0) e que
não contenha o par (-i, -j) pode ser extendida a uma combinação de n + 1
elementos cuja soma seja (0, 0).
Precisamos primeiro determinar quantas combinações de n elementos tem soma
(i, j) e não contenham (-i, -j). Ou seja, excluímos as combinações que
possuem (-i, -j) e n - 1 elementos com soma (2i, 2j), e que não possua
(-i, -j) novamente...

Tendo como:
q[k] := número de combinações de k elementos com soma (0, 0)
t[k] := número de combinações de k elementos com soma diferente de (0, 0)

Quando chegarmos em (m*i, m*j) com p | m, usamos o valor de q para
estabelecer a recorrência.
Ok, suponhamos então que já nos seja dado um valor r[k] com o número de
combinações de k elementos cuja soma seja (i, j) e a comb. não contenha
(-i, -j).
Não podemos afirmar diretamente que q[k+1] = (p²-1).r[k] pois pode ser que
duas combinações diferentes, ao seguir o processo descrito acima, originem
uma mesma combinação...
Felizmente isso só pode acontecer em um caso bem estrito: para que esse
conflito ocorra as duas combinações originais só podem diferir em UM
elemento.

u != v pertence a Zp X Zp e S um subconjunto de Zp X Zp
C1 = { u } U S
C2 = { v } U S

Suponha que u + v + Somatório{ w pert. S } = (0, 0).
Se inserirmos v em C1 e u em C2 o conjunto resultante, { u, v } U S é o
mesmo...

Acho que eliminando esse caso estrito o problema pode ser resolvido, mas eu
estou sem paciência para tentar esse caminho tortuoso! Quem sabe alguém se
habilita!

Obrigado pela atenção!

[ ]'s

Domingos.

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