Re: [obm-l] Roleta

["Fabio Dias Moreira" <fabio@xxxxxxxxxxxxxxxxxxx>]

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