Oi Nicolau.
Você tem razão, parece que não existem atalhos para o problema 2).
Na verdade a colocação da expressão "outra versão" entre as perguntas 1) e
2) dá á impressão de uma vinculação entre elas que, se existe, esta longe
de ser óbvia, como sugerido.
Do primeiro problema, onde se pede para determinar o número de partições de
C={1,2,.....2007} em dois subconjuntos disjuntos com mesma soma, pode-se
concluir que, uma vez determinado esse número estará determinado um número
igual de zeros obtido a partir do enunciado do problema 2), porém sem
maiores considerações de natureza probabilísticas, como detalhei no problema
1).
E assim estaria resolvido também o problema 2).
O fato, porém é que, infelizmente, a recíproca não é verdadeira. Pois
quando uma das distrubuições aleatorias dos + e - conduz a uma configuração
de soma zero, o conjunto de referência desta soma já não será mais o
original, o conjunto C, que teria sido desfigurado pelas variações
fortuitas até o evento da ocorrencia da soma zero. Não teríamos obtido
então uma partição de C em dois conjuntos disjuntos, de soma igual, mas
sim de um outro conjunto diferente. Assim haverá muito mais zeros do que o
número de subconjuntos com soma igual, pedido no primeiro problema. O que
aliás seria de esperar, dada a enormidade de configurações possíveis
resultantes da aplicação da regra de 2) e o número grande, porém de ordem
de grandeza muitas vezes menor, dos conjuntos pedidos no problema 1)
Agora vou mergulhar no material que você e o Santa
Rita disponibilizaram, para ver ( se entendo...) e se é possivel prosseguir
na linha que adotei para o problema 1), ou seguir outra mais adequada, e
ver se posso avançar no 2).
Abraços
Candeias
Em 08/11/07, Nicolau C. Saldanha <[EMAIL PROTECTED]> 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).
>
> Acho muito improvável que haja uma expressão simples para a resposta
> deste problema.
> Veja um pouco sobre a generalização deste problema (trocando 2007 por n)
> aqui:
>
> http://www.research.att.com/~njas/sequences/A058377
>
> Outra expressão para a probabilidade 2^(-n)*a[n] é
>
> (1/(2*pi)) integral_0^(2 pi) cos(t) cos(2t) cos(3t) ... cos(nt) dt
>
> Para ver isso, escreva cos(kt) = (z^k + z^(-k))/2 onde z = exp(it).
> A probabilidade (ou número de combinações dividido por 2^n) é,
> conforme o Paulo Santa Rita explicou, o coeficiente independente
> que é obtido integrando e dividindo por 2 pi.
>
> Esta expressão permite estimar a probabilidade pois longe de 0 e pi
> o produto fica muito próximo de 0.
> Para t perto de 0, fazendo
> cos t ~= 1 - t^2/2 ~= exp(-t^2/2) e portanto cos(kt) ~= exp(-k^2 t^2/2)
> temos
> cos(t) cos(2t) cos(3t) ... cos(nt) ~= exp(-(1^2 + .. + n^2)t^2/2) ~=
> exp(-(n^3/3) t^2/2)
> Ora, sabemos que integral exp(-a t^2/2) = sqrt(2 pi/a) donde a parte da
> integral
> perto de 0 é aproximadamente sqrt(6 pi/n^3).
> Se n(n+1)/2 for ímpar a integral perto de pi cancela com esta para dar 0
> mas se n(n+1) for par a integral perto de pi dá igual donde a
> probabilidade
> dá aproximadamente sqrt(24 pi/n^3)/2 pi = sqrt(6/(pi*n^3)).
>
> Para n=63 usei o maple para calcular a probabilidade exata e para a
> fórmula acima.
> As resopstas foram 0.002711775516 (primeiro calculando a probabilidade
> exata
> e depois fazendo o quocente aproximado) e 0.002763693420 (pela fórmula).
> Para n = 83 obtive 0.001801463390 e 0.001827610102 , respectivamente.
> Para n = 2007 o maple não conseguiria fazer a conta exata (pelo menos
> não da forma
> como eu programei) mas a fórmula dá 0.00001537020394;
> deve estar bem perto da resposta certa.
>
> N.
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================
>
--
Fernando A Candeias
