Re: [obm-l] Probabilidade

["Paulo Santa Rita" <paulo.santarita@xxxxxxxxx>]

Ola Fernando e demais
colegas desta lista ... OBM-L,

Responder esta pergunta exige a solucao de um problema combinatorio
previo, qual seja, o de determinar de quantas maneiras distintas
podemos distribuir os elementos do conjunto A={ 1, 2, 3,..., 2007 } em
dois outros conjuntos DISJUNTOS A e B de maneira que a soma dos
elementos de B seja igual a soma dos elementos de C. Vou reformular
este enunciado.

Seja A = { 1, 2, 3, ..., 2007 }. Queremos saber de quantas maneiras
distintas podemos exprimir A na forma A = B uniao C, onde :

1) B intersecao C = Conjunto Vazio
2) Soma dos elementos de B = Soma dos elementos de C

Como 1 + 2 + 3 + ... + 2007 = (2007*(1+2007))/2 = 2015028 e claro que
a soma dos elementos de B ( e, claro, de C também ) deverá ser 2015028
/ 2 = 1007514. E e igualmente claro que para um determinando conjunto
B com elementos oriundos de A e cuja soma destes elementos seja
1007514, o correspondente conjunto C que atende as exigencias 1) e 2)
acima fica automaticamente determinado, C = A – B. Assim, precisamos
nos preocupar apenas em determinar

( PRIMEIRA REFORMULACAO DO PROBLEMA )

( ENUNCIADO1 ) Quantos conjuntos B podemos construir tais que os seus
elementos sejam oriundos de A e que a soma destes elementos seja
1007514.

Seja entao B = {b1, b2, b3, ..., bn } um destes conjuntos. Como
1007514 = b1+b2+...+bn e bi promana de A, vale dizer, bi e inteiro
positivo, segue que "b1+b2+...+bn" e uma PARTICAO do numero  1007514.
Ora, uma particao de um inteiro positivo N e uma soma de inteiros
positivos, i1 + i2 + ... + in, distintos ou não, tais que N = i1 + i2
+ ... + in. Logo, os conjuntos B que estamos buscando são em verdade
todas as particoes de 1007514 que atendam as seguintes restricoes  :

1) As parcelas  devem ser duas a duas distintas
2) Nenhuma parcela pode ser superior a 2007

Esta ultima consideracao deixa claro que o que buscamos pode ser
expresso assim :

( SEGUNDA REFORMULACAO DO PROBLEMA )

( ENUNCIADO2 ) Quantas particoes de 1007514 podemos construir tais que
as parcelas de cada particao sejam duas a duas distintas e nenhuma
delas seja superior a 2007.

Vamos nos fixar aqui. A principio, definimos a sequencia de polinomios :

P0 = 1
Pi = ( 1 + (X^i) )*Pi-1,   i = 1, 2, 3, ...

Analisando a sequencia acima, e facil ver que

1) Todo Pi tem termo independente e coeficiente lider iguais a 1
2) Todo Pi e um polinomio completo cujo grau e (i(1+i))/2

Um fenomeno notavel - facilmente observavel e simples de explicar – e
que, para todo "n",  um monomio com parte literal X^n surgira pela
primeira vez na sequencia de polinomios no polinomio Pi tal que "i"
seja o menor inteiro positivo tal que (i*(1+i))/2 >= n. Isso
claramente decorre do fato de Pi ser completo e de grau (i*(1+i)) / 2
. E igualmente facil de ver que, após surgir, o coeficiente de X^n
cresce ate atingir o seu valor maximo no polinomio Pn.

Os coeficientes de X^n nos polinomios Pi onde ele aparece fornece
informacoes importantes sobre as particoes de "n" em parcelas duas a
duas distintas ... com efeito, dado que Pi = (1+ X )*(1 + (X^2) )*(1 +
(X^3) )*...*(1+ (X^i) ), ao efetuar as multiplicacoes indicadas, um
produto de ate "i" monomios da forma X^e, 1 =< e  =< i, vai contribuir
para a formacao final do coeficiente de X^n se a soma dos seus
expoentes for "n", vale dizer, o coeficiente de X^n em Pi, i =< n, e
igual ao numero de particoes de "n" em parcelas duas a duas distintas,
todas menores que i+1. Por esta razao, o que estamos buscando pode ser
 expresso assim :

( TERCEIRA REFORMULACAO DO PROBLEMA )

( ENUNCIADO3 ) Qual e o coeficiente de X^1007514 em P2007 ?

Assim, fica claro a ligacao deste problema com a Teoria das Particoes.
Este tema da teoria dos numeros e bastante amplo e antigo, com belas
contribuicoes de Euler, Ramanujam e outros. O livro abaixo, elementar
e introdutorio, trata desse tema :

Introducao a Teoria dos Numeros
Colecao Matematica Universitaria - IMPA
Autor

Voce tambem pode ver isso aqui :

http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf

Um Abraco a Todos
Paulo Santa Rita
4,0738,070A07

Em 05/11/07, fernando.cores<fernando.cores@xxxxxxxxxxxx> escreveu:
>
> Problema de combinatória II
>
>                                Escrevem-se em um quadro negro os primeiros
> 2007 números naturais: 1, 2, 3, ..., 2007. A frente de cada um se escreve o
> sinal + ou - de forma ordenada, da esquerda para direita. Para decidir cada
> sinal é jogada uma moeda: se sai cara escreve- se + (mais), se sai coroa
> escreve -se - (menos). Uma vez escritos os 2007 sinais efetua - se a soma da
> expressão resultante. Determinar a probabilidade de que o resultado seja 0.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================