Re: [obm-l] Combinatória

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

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

 

Complementando.

Esta segunda parte do problema, parece estar intimamente relacionada com a primeira.

Supondo que foram identificados os N conjuntos do problema anterior. Seriam subconjuntos disjuntos de C={1,2,3....2700}, resultantes de sua divisão, e que poderiam ser grupados em pares (N/2 pares) :(D1,E1); (D2,E2)...(Dn,En), onde C=(Di U Ei).  Pela  primeira parte do problema  devemos ter:(Di=Ei)

Agora formemos os pares auxiliares (D1,-E1);(D2,-E2)....(Dn,-En).

Quando aplico a condição probabilistica  de 2) vou obter resultados que variam entre -S e +S sendo S a soma dos elementos do conjunto C={ 1,2,3,....2007} que é igual a 2.015.028.

Todos os valores intermediários  serão obtidos pelo menos uma vez. ( Possivelmente muitas vezes, já que o número total  de possibilidade é gigantesco: 2^2007)).

Cada vez que algum dos  valores -E1,-E2 ...-En for atingido, a soma dos elementos do conjunto C será anulada..

O que acontecerá N/2 vezes, se  N for par ou uma só vez, se for ímpar. 

 

Em 07/11/07, Fernando A Candeias <facandeias@xxxxxxxxx> escreveu:

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

-- 
Fernando A Candeias