Re: [obm-l] Problema 6 da OBM de 2002

2015-10-12 Por tôpico Bernardo Freitas Paulo da Costa 
2015-10-12 0:31 GMT-03:00 Gabriel Tostes :
> Mostre que não podemos formar mais que 4096 sequências binárias de tamanho 24 
> tal que quaisquer 2 diferem em ao menos 8 posições.
> Não consegui entender a resolução na Eureka. Alguém pode resolvê-lo?

Eu não sei se conheço alguma solução além da do Fábio (imagio que seja
esta a da Eureka). Mas acredito que pode ajudar a entender o problema
diminuindo os números, e tentando ser mais ambicioso: tente descobrir
a maior quantidade de sequências binárias de tamanho 4 tais que duas
quaisquer diferem em ao menos 2 posições. Vou tentar começar o
raciocínio: Suponha, sem perda de generalidade, que uma das sequências
é a . Então, você não pode ter nenhuma sequência com apenas um
"1", certo? Agora, pense em quantas sequências com dois "1" podem
haver. Ao todo, há 6, mas você não pode escolher todas elas, certo?

Para completar, ainda falta a idéia das "regiões de influência" (cada
sequência escolhida "domina" algumas sequências, as que estão mais
próximas dela do que de qualquer outra sequência). Para visualisar
isso, pense que, em vez de 4/2, o problema é sobre tam=5 / diferença
>= 3. Faça um "ponto" para cada sequência (dá 32, dá trabalho mas é
factível) e ligue as que diferem de apenas uma posição. Daí, comece
marcando uma (tipo a 0) e depois vá escolhendo como puder. Isso
deve deixar claro para você que cada sequência tem uma região de
influência de tamanho 1.

Abraços,
-- 
Bernardo Freitas Paulo da Costa

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


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

RE: [obm-l] Problema 6 da OBM de 2002

2015-10-12 Por tôpico Esdras Muniz 
Em qual EUREKA está a solução deste problema?


-Mensagem Original-
De: "Bernardo Freitas Paulo da Costa" 
Enviada em: ‎12/‎10/‎2015 12:29
Para: "Lista de E-mails da OBM" 
Assunto: Re: [obm-l] Problema 6 da OBM de 2002

2015-10-12 0:31 GMT-03:00 Gabriel Tostes :
> Mostre que não podemos formar mais que 4096 sequências binárias de tamanho 24 
> tal que quaisquer 2 diferem em ao menos 8 posições.
> Não consegui entender a resolução na Eureka. Alguém pode resolvê-lo?

Eu não sei se conheço alguma solução além da do Fábio (imagio que seja
esta a da Eureka). Mas acredito que pode ajudar a entender o problema
diminuindo os números, e tentando ser mais ambicioso: tente descobrir
a maior quantidade de sequências binárias de tamanho 4 tais que duas
quaisquer diferem em ao menos 2 posições. Vou tentar começar o
raciocínio: Suponha, sem perda de generalidade, que uma das sequências
é a . Então, você não pode ter nenhuma sequência com apenas um
"1", certo? Agora, pense em quantas sequências com dois "1" podem
haver. Ao todo, há 6, mas você não pode escolher todas elas, certo?

Para completar, ainda falta a idéia das "regiões de influência" (cada
sequência escolhida "domina" algumas sequências, as que estão mais
próximas dela do que de qualquer outra sequência). Para visualisar
isso, pense que, em vez de 4/2, o problema é sobre tam=5 / diferença
>= 3. Faça um "ponto" para cada sequência (dá 32, dá trabalho mas é
factível) e ligue as que diferem de apenas uma posição. Daí, comece
marcando uma (tipo a 0) e depois vá escolhendo como puder. Isso
deve deixar claro para você que cada sequência tem uma região de
influência de tamanho 1.

Abraços,
-- 
Bernardo Freitas Paulo da Costa

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


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

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Re: [obm-l] Probabilidade de que o número de sucessos seja par

2015-10-12 Por tôpico Lucas Prado Melo 
Correção: a recorrência é Pn = p (1-P(n-1)) + (1-p) P(n-1)

2015-10-12 21:42 GMT-03:00 Lucas Prado Melo :

> É possível mostrar que Pn = p *( 1-  P(n-1)) + (1-p) Pn
>
> Disso conclui-se que Pn = p + (1-2p)P(n-1)   e, dividindo a equação por
> (1-2p)^n (para p != 1/2), encontramos uma formula fechada para Pn/(1-2p)^n.
>
> Finalmente chegamos que Pn = (1 + (1-2p)^n)/2, mesmo quando p = 1/2.
>
> 2015-10-12 20:17 GMT-03:00 Amanda Merryl :
>
>>
>> Oi amigos
>>
>> Um experimento tem probabilidade p de sucesso. Em n realizaçŠes
>> independentes do mesmo, qual a probabilidade Pn de que o número de
>> sucessos seja par? Há uma fórmula  fechada para Pn?
>>
>> Devemos ter lim n --> oo Pn = 1/2, certo?
>>
>> Obrigada.
>>
>> Amanda
>>
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>>  acredita-se estar livre de perigo.
>>
>>
>> =
>> Instruções para entrar na lista, sair da lista e usar a lista em
>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
>> =
>>
>
>
>
> --
> []'s
> Lucas
>



-- 
[]'s
Lucas

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Re: [obm-l] Probabilidade de que o número de sucessos seja par

2015-10-12 Por tôpico Marcelo Salhab Brogliato 
Olá, Amanda,

Você pode usar a fórmula da distribuição binomial, restringindo apenas aos
valores pares. Assim:
Pn = \sum_{k=0..piso(n/2)} C(n, 2k) * p^{2k} (1-p)^{n - 2k}, onde C(n, 2k)
= n! / [(2k)! (n - 2k)!].

Mas acho que fica difícil calcular lim{n-> inf} Pn usando essa equação.

Para resolver com n -> inf, acho que o mais fácil é encontrar uma recursão.

Veja que existem duas formas de termos uma quantidade par com n+1
realizações. Ou com n é par e temos um insucesso, ou com n é impar e temos
um sucesso. Assim:

P{n+1} = p(1 - Pn) + (1-p)*Pn, com P0 = 1.

Como essa é uma recursão linear, é fácil encontrar uma fórmula fechada para
ela. Fica como exercício pra você. :)

Para o limite, quando n -> inf, e supondo que Pn converge, temos:
lim{n->inf} Pn = a.
Assim:
a = p(1-a) + (1-p)*a
a = p - pa + a - pa
2pa = p
a = 1/2

Assim, se Pn convergir, ele irá convergir para 1/2. Falta só provar que Pn
converge quando n -> inf. Fica como exercício pra você. :)

Obs: Dá para mostrar que converge usando apenas desigualdades.
Obs2: Com a fórmula fechada, é bem fácil mostrar que Pn converge.

Abraços,
Marcelo

2015-10-12 20:17 GMT-03:00 Amanda Merryl :

>
> Oi amigos
>
> Um experimento tem probabilidade p de sucesso. Em n realizaçŠes
> independentes do mesmo, qual a probabilidade Pn de que o número de
> sucessos seja par? Há uma fórmula  fechada para Pn?
>
> Devemos ter lim n --> oo Pn = 1/2, certo?
>
> Obrigada.
>
> Amanda
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
>  acredita-se estar livre de perigo.
>
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

Re: [obm-l] Probabilidade de que o número de sucessos seja par

2015-10-12 Por tôpico Ary Medino 
Cara Amanda
Suponho que o experimento a que se refere admite apenas dos resultados: Um 
chamado de "sucesso", com probabilidade 0 < p < 1 de ocorrer, e outro chamado 
de "fracasso", com probabilidade 1 - p de ocorrer. Experimentos aleatórios com 
essas características são chamados de "ensaios de Bernoulli". Em n realizações 
independentes de tais experimentos, isto é, n ensaios de Bernoulli 
independentes, o número de sucessos tem distribuição Binomial com parâmetros n 
e p. Ou seja, a probabilidade de se obter k sucessos em n ensaios é dada por 
B(n,k)p^k(1 - p)^(n-k), onde B(n,k) é o número Binomial n tomados k a k.A 
probabilidade Pn que você busca, isto é, a probabilidade de se obter um número 
par de sucessos em n ensaios de Bernoulli independentes,  é a soma dos valores 
B(n,k)p^k(1 - p)^(n-k) com k restrito aos números pares de 0 a n.
Você pode fazer uma busca na internet por esses termos para saber maisAbraçoAry 


 Em Segunda-feira, 12 de Outubro de 2015 20:46, Amanda Merryl 
 escreveu:
   

 
Oi amigos

Um experimento tem probabilidade p de sucesso. Em n realizaçōes independentes 
do mesmo, qual a probabilidade Pn de que o número de sucessos seja par? Há uma 
fórmula  fechada para Pn?

Devemos ter lim n --> oo Pn = 1/2, certo?

Obrigada.

Amanda


-- 
Esta mensagem foi verificada pelo sistema de antiv�us e
 acredita-se estar livre de perigo.


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


  
-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Re: [obm-l] Probabilidade de que o número de sucessos seja par

2015-10-12 Por tôpico Artur Costa Steiner 
Sendo X a variável aleatória número de sucessos nas n realizações, X tem
distribuição binomial com parâmetros n e p (estou supondo que só há dois
resultados possíveis, sucesso e fracasso, é um experimento de Bernouille se
0 < p < 1)

Assim, para k = 0, 1,... n, P(X = k) = C(n, k) p^k (1 - p)^(n - k), C(n, k)
a combinação de n, k a k.

Desta forma, Pn é obtida somando-se os termos acima para os valores pares
de k, ou seja

Pn = Soma (k par) C(n, k) p^k (1 - p)^(n - k)

No somatório de Pn, k vai de 0'até o maior par menor ou igual a n.

Para obtermos uma fórmula fechada para Pn, observemos que, pelo Binômio de
Newton,

C(n, 0) p^0 (1 - p)^(n) +  C(n, 1) p^1 (1 - p)^(n - 1) +  C(n, n) p^n
(1 -p)^0 = 1

C(n, 0) (-p)^0 (1 - p)^(n)  + C(n, 1) (-p)^1 (1 - p)^(n - 1) +  C(n, n)
(-p)^n (1 -p)^0 = C(n, 0) (p)^0 (1 - p)^(n)  - C(n, 1) (-p)^1 (1 - p)^(n -
1) +  C(n, n) (-p)^n (1 -p)^0 = (-p + 1 - p)^n = (1 - 2p)^n

No segundo somatório, substituímos p por - p e mantivemos 1 - p. Assim, os
termos com k par se mantém e os com k ímpar permutam seu sinal. Desta
forma, somando as duas equações e considerando a definição de Pn, obtemos

2 Pn = 1 + (1 - 2p)^n

Pn = (1 + (1 - 2p)^n)/2

E se vc quiser a prob. de que haja um número ímpar de sucessos, chega a 1 -
Pn =  (1 -(1 - 2p)^n)/2.

Se p estiver em (0, 1) (experimento de Bernouille), então |1 - 2p| < 1, (1
-2p)^n --> 0 e, portanto, temos de fato que Pn --> 1/2. Isto bate com a
intuição. Não há nenhum motivo para que, à medida em que se aumenta n, os
estados pares sejam mais visitados que os ímpares, e vice versa.

Mas se p = 0, só há fracassos, temos sempre 0 sucessos, que é par, e Pn = 1
para todo n. o que é confirmado pela fórmula acima. Logo, o limite é 1,

Se p = 1, há sempre n sucessos e Pn = 1 se n for par e Pn = 0 se n for
ímpar. Logo, não existe limite quando n --> oo.

Abraços



Artur Costa Steiner

Em 12 de out de 2015, às 21:17, Ary Medino 
escreveu:

Cara Amanda

Suponho que o experimento a que se refere admite apenas dos resultados: Um
chamado de "sucesso", com probabilidade 0 < p < 1 de ocorrer, e outro
chamado de "fracasso", com probabilidade 1 - p de ocorrer.
Experimentos aleatórios com essas características são chamados de
"ensaios de Bernoulli".
Em n realizações independentes de tais experimentos, isto é, n ensaios
de Bernoulli independentes, o número de sucessos tem distribuição
Binomial com parâmetros n e p. Ou seja, a probabilidade de se obter k
sucessos em n ensaios é dada por B(n,k)p^k(1 - p)^(n-k), onde B(n,k) é o
número Binomial n tomados k a k.
A probabilidade Pn que você busca, isto é, a probabilidade de se obter um
número par de sucessos em n ensaios de Bernoulli independentes,  é a soma
dos valores B(n,k)p^k(1 - p)^(n-k) com k restrito aos números pares de 0 a
n.

Você pode fazer uma busca na internet por esses termos para saber mais
Abraço
Ary



Em Segunda-feira, 12 de Outubro de 2015 20:46, Amanda Merryl <
sc...@hotmail.com> escreveu:



Oi amigos

Um experimento tem probabilidade p de sucesso. Em n realizaçōes
independentes do mesmo, qual a probabilidade Pn de que o número de
sucessos seja par? Há uma fórmula  fechada para Pn?

Devemos ter lim n --> oo Pn = 1/2, certo?

Obrigada.

Amanda


-- 
Esta mensagem foi verificada pelo sistema de antiv�us e
acredita-se estar livre de perigo.


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



-- 
Esta mensagem foi verificada pelo sistema de antivírus e
acredita-se estar livre de perigo.


Em segunda-feira, 12 de outubro de 2015, Amanda Merryl 
escreveu:

>
> Oi amigos
>
> Um experimento tem probabilidade p de sucesso. Em n realizaçŠes
> independentes do mesmo, qual a probabilidade Pn de que o número de
> sucessos seja par? Há uma fórmula  fechada para Pn?
>
> Devemos ter lim n --> oo Pn = 1/2, certo?
>
> Obrigada.
>
> Amanda
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
>  acredita-se estar livre de perigo.
>
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Probabilidade de que o número de sucessos seja par

2015-10-12 Por tôpico Amanda Merryl 

Oi amigos

Um experimento tem probabilidade p de sucesso. Em n realizaçōes independentes 
do mesmo, qual a probabilidade Pn de que o número de sucessos seja par? Há uma 
fórmula  fechada para Pn?

Devemos ter lim n --> oo Pn = 1/2, certo?

Obrigada.

Amanda


-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.


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

[obm-l] Re: [obm-l] Probabilidade de que o número de sucessos seja par

2015-10-12 Por tôpico Lucas Prado Melo 
É possível mostrar que Pn = p *( 1-  P(n-1)) + (1-p) Pn

Disso conclui-se que Pn = p + (1-2p)P(n-1)   e, dividindo a equação por
(1-2p)^n (para p != 1/2), encontramos uma formula fechada para Pn/(1-2p)^n.

Finalmente chegamos que Pn = (1 + (1-2p)^n)/2, mesmo quando p = 1/2.

2015-10-12 20:17 GMT-03:00 Amanda Merryl :

>
> Oi amigos
>
> Um experimento tem probabilidade p de sucesso. Em n realizaçŠes
> independentes do mesmo, qual a probabilidade Pn de que o número de
> sucessos seja par? Há uma fórmula  fechada para Pn?
>
> Devemos ter lim n --> oo Pn = 1/2, certo?
>
> Obrigada.
>
> Amanda
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
>  acredita-se estar livre de perigo.
>
>
> =
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>



-- 
[]'s
Lucas

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.