Re: [obm-l] Uma de probabilidade...

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Caro Marcos,
   Temos (1+x)^2^m=1+x^2^m (mod 2). Assim, se k(1)>k(2)>...>k(r),
(1+x)^(2^k(1)+2^k(2)+...+2^(k(r))=(1+x^2^k(1))(x^2^k(2))...(1+x^2^k(r)) 
(mod 2), e isso tem 2^r coeficientes iguais a 1 e os outros iguais a 0.
Assim, se m tem r bits não nulos, ha' 2^r valores de k com 0<=k<=m tais que
Binomial(m,k) é ímpar. Se m<2^n, m é uma soma de potências de 2 com
expoentes entre 0 e n-1. Há Binomial(n,r) tais somas com r parcelas. Assim,
o número de pares (k,m) com 0<=k<=m<2^n e Binomial(m,k) ímpar é dado por 
soma(r=0 a n)(Binomial(n,r).2^r)=3^n (para m=2^n haverá dois outros pares,
(0,2^n) e (2^n,2^n), mas isto não afetará a probabilidade), e o número total 
dos pares (k,m) com 0<=k<=m<2^n é 1+2+...+2^n=2^(n-1)(2^n+1)>(1/2).4^n. Como
lim 3^n/4^n=0, temos lim Pn=0.
   Abraços,
            Gugu

>
>   Olá pessoal da lista! Preciso da ajuda de vocês no seguinte
>problema. Consegui resolvê-lo e queria conferir minha resposta.
>   Dado n natural, escolhemos k em também naturais tais que
>0<=k<=m<=2^n. Seja Pn a probabilidade do coeficiente binomial ser par.
>Encontre lim Pn.
>   Obrigado!
>
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>=========================================================================
>

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