RES: [obm-l] Roleta

["Guilherme" <gui@xxxxxxxxxx>]

Olá, Fábio!

Incrível!!! Muito obrigado mesmo!

Um abração!

Guilherme Marques.


-----Mensagem original-----
De: owner-obm-l@mat.puc-rio.br [mailto:owner-obm-l@mat.puc-rio.br] Em
nome de Fabio Dias Moreira
Enviada em: domingo, 27 de fevereiro de 2005 11:19
Para: obm-l@mat.puc-rio.br
Assunto: Re: [obm-l] Roleta

Guilherme said:
> Olá, pessoal!
>
> Recebi um pedido, há alguns dias, de um amigo que mora na Bélgica. Ele
> pediu que eu calculasse para ele, em N rodadas de uma roleta (37
> números, de 0 a 36), qual a probabilidade de pelo menos um número dos
37
> não aparecer.

Eu vou resolver não o seu problema, mas o seguinte problema: em quantas
sequências do conjunto {0, 1, ..., 36}^N algum dos números de 0 a 36 não
figura? Supondo que todos os números da roleta são equiprováveis, e se R
é
a resposta desse problema, basta achar R/37^N.

Quantas seqüencias existem tais que nenhum dos números k_1, k_2, ...,
k_p
figura na seqüencia? Claramente, a resposta é (37-p)^N.

Se S_k é o conjunto das seqüências que não contém k, temos que

#(S_0 união S_1 união ... união S_36) =
= soma(p = 1..37) soma(0 <= k_1 < k_2 < ... < k_p <= 36) (-1)^(p+1)
#(S_k_1 inter S_k_2 inter ... inter S_k_p) =
= soma(p = 1..37) soma(0 <= k_1 < k_2 < ... < k_p <= 36) (-1)^(p+1)
(37-p)^N

pelo Princípio da Inclusão-Exclusão. Como o somatório interno não
depende
dos k_p, a soma acima é claramente igual a

soma(p = 1..37) (-1)^(p+1) C(37;p) (37-p)^N.

Como o somatório externo tem limites superior e inferior fixos, a
fórmula
encontrada é fechada.

(Eu fiz um programa em Python para testar a fórmula, e ele concorda com
todos os casos iniciais que você colocou no seu email.)

[]s,

-- 
Fábio Dias Moreira


========================================================================
=
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
=========================================================================