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

Re: [obm-l] Combinatória



Retificando.
O número é necessáriamente par. SoluçãoN/2.

 
Em 08/11/07, Fernando A Candeias <facandeias@xxxxxxxxx> escreveu:
 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



--
Fernando A Candeias