Re: [obm-l] Combinatória

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

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 <nicolau@xxxxxxxxxxxxxx > 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