Re: [obm-l] Combinatória

["Fernando A Candeias" <facandeias@xxxxxxxxx>]

Oi Fernando

Pensei numa abordagem prática, mas  que pode ajudar na solução do problema.

1) A partir de dois subconjuntos disjuntos C_1 e C_2 do conjunto C={1,2,....2007} é possível construir qualquer outro par de subconjuntos disjuntos , por transferências ou trocas  entre os elementos de C_1 e C_2. Portanto, se existir um desses pares cuja soma dos elementos seja igual, esse par poderá ser obtido a partir de qualquer outro par de subconjuntos disjuntos. A idéia é então construir um desses pares, um par bem comportado, e mostrar que a partir dele é possivel construir vários outros pares cuja soma dos elementos seja igual. E contar o número deles. O  que, pelo dito, constituiria  a totalidade possível de conjuntos disjuntos com mesma soma de elementos.

Escolhi os subconjuntos disjuntos C_1={1,3,5......2007} e  C_2={2,4,6,....2006}.  As somas S1 e S2 em cada  sub conjunto são pares. Alem disso é facil verificar que   S1-S2=1004. 

Para  igualar as somas S1 e S2 será necessário fazer  transferências ou trocas entre  C_1 e C_2, mas cujo resultado líquido seria equilalente a transferir uma parcela de soma de C_1 para C_2 igual a 502. O que significaria selecionar entre os ímpares de C_1 certo número de elementos com essa soma. 

Naturalmente começando por pares, depois quadruplas etc.. sempre números pares de números ímpares da sequencia C_1.

Logo identifico os pares (1,501), (3,499), (5,497) e muitos outros que migrariam de C_1 para C2 e tornariam S1=S2. Como 502 é um número relativamente pequeno, deverá haver uma maneira fcail de identificar esses pares , quadruplas etc.. uma lei de formação, coisa assim.

O que parece mais importante, e se meu raciocínio anterior está certo, é que eles esgotariam o problema.

Abraços

Candeias

Em 04/11/07, fernando.cores <fernando.cores@xxxxxxxxxxxx > escreveu:

Amigos, se alguém puder ajudar, no seguinte problema, eu agradeço

 

   1) De quantas formas podemos dividir o conjunto {1, 2, 3, ..., 2007} em dois suconjuntos disjuntos, tais que a soma de seus elementos seja igual?

 

outra versão

 

  2) Distribuindo aletoriamente os sinais "+' ou "-" a frente dos números 1, 2, 3, ..., 2007, quantas configurações há tal que o resultado final seja 0(zero).

 

                desde já obrigado

-- 
Fernando A Candeias