[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Combinatória



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