[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Probabilidade
Olá Paulo, Fernando e demais colegas:
A solução e as observações do Paulo acerca do problema são realmente
brilhantes. Quando li a questão, inicialmente não imaginei resolver como
um problema de partiçoes de inteiros, embra me pareça que
ser a solução do Paulo seja a única forma correta neste caso,
pelo que andei analisando.
Problemas de partições de inteiro são problemas bastante estudados.
A primeira vez que me deparei com essas questões foi lendo o seguinte paper:
http://www.math.upenn.edu/~wilf/PIMS/PIMSLectures.pdf
Nele o leitor pode constatar que existe uma fórmula bastante interessante que
dá o número de partições exato de qualquer inteiro n. Essa fórmula está
na página 14 do paper acima.
Abraços a todos.
Paulo Santa Rita wrote:
> Ola Fernando e demais
> colegas desta lista ... OBM-L,
>
> Eu so respondi por dois motivos :
>
> 1) Tornar claro a ligacao do problema com o tema das particoes tanto
> para facilitar a solucao de alguem que venha a ter interesse pela
> questao como para colocar em pauta aqui na lista este tema da teoria
> dos numeros ( particoes ), muito pouco abordado.
>
> 2) O tipo de problema me levou a imaginar que voce fosse um
> pesquisador na area de Computacao e estava querendo testar a
> eficiencia de algum sistema de codificacao de mensagem tal que tomando
> dois subconjuntos disjuntos B e C de A={1, 2, ..., N }, N nao tao
> grande, com mesma soma dos elementos, ao transmitir a mensagem
> codificada com B um outro usuario facilmente encontraria C e
> decodificaria, enquanto que uma pessoa estranha nao-autorizada - tendo
> inteceptado a mensagem - dado a grande quantidade de possibilidades,
> teria muita dificuldade numa decodificacao nao-autorizada.
>
> O caso 2) seria interessante se fosse viavel para N "nao tao grande",
> pois significaria um aperfeicoamento em relacao ao que se faz
> rotineiramente hoje ( numero primo "grande" ). Entretanto, vejo que
> imaginei errado ... Como voce diz que isto e apenas um problema
> olimpico, eu procuraria uma solucao bem elementar, por exemplo :
>
> 1) E claro que existe UMA UNICA solucao de COMPRIMENTO MINIMO,
> nomeadamente, comecando com uma PA decrescente de primeiro termo 2007
> e razao -1. Talvez seja necessario acrescentar um menor termo que nao
> faca parte da PA. Chamarei esse cara de N. Mas ela tera a forma :
>
> N + ( (P) + (P+1) + (P+2) + ...+ 2007) =1007514
>
> 2) E claro que vai haver uma solucao de COMPRIMENTO MAXIMO, com a forma :
>
> 1 + 2 + ... + Q + N = 1007514
>
> 3) Classificando-se as solucoes pelos comprimentos talvez fique mais
> facil encontra-las.
>
> Nao pensei no problema, mas fica a sugestao
>
> Um Abraco
> Paulo Santa Rita
> 4,0B23,070B07
>
> Em 07/11/07, fccores<fccores@xxxxxxxxxx> escreveu:
> > Prezado Paulo Santa Rita,
> >
> > Primeiramente obrigado por sua detalhada e clara explicação do
> > problema, apesar de também ter chegado a esta conclusão, de que os casos
> > favoráveis correspondem justamente ao coeficiente de x^(502*2007). Fato este
> > que me levou a consultar várias fontes, inclusive "Introdução à análise
> > combinatória", do mesmo autor do compêndio ao qual você se refere, na busca
> > de assuntos que ajudassem como: funções geradoras e partições de um inteiro.
> > Estudei, inclusive um outro problema correlato:
> >
> > "Determinar o coeficiente de x^k, 0=<k=<n, no desenvovimento de [1 +
> > ax].[1 + (a^2)x]...[1 + (a^n)x]."
> >
> > Em verdade, o problema se resume, agora, a determinar uma maneira
> > explícita (ou elementar) de calcular tal coeficiente, por isso esperava
> > (espero), talvez outras abordagens para aquele problema, já que o mesmo é um
> > problema olímpico, que me foi enviado por um amigo do Chile. Formulei
> > algumas outras conjecturas acerca do problema, como por exemplo que aquele
> > coeficiente é uma potência de 2, estou trabalhando na prova.
> >
> > Enfim, mais uma vez agradeço a clara e precisa mensagem e
> > parabenizo a todos pelas excelentes e frutíferas discussões desta lista, da
> > qual sou um leitor assíduo.
> >
> > Fernando Córes
> >
> >
> > > 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
> > >
> > =====================================================================
> > > Instruções para entrar na lista, sair da lista e usar a lista em
> > > http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> > >
> > =========================================================================
>
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =========================================================================
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================