[obm-l] [obm-l] Probabilidade em amigo oculto - SOLUÇÃO

["Rogerio Ponce" <rogerio_ponce@xxxxxxxxxxx>]

Olá pessoal,
qual a probabilidade P(N) de ocorrer um sorteio válido numa reunião de N 
"amigos ocultos" ?
(sorteio válido é aquele em que ninguém sorteia a si mesmo).

-------------

Primeiramente, em um sorteio qualquer, existem sub-grupos do tipo "A sorteia 
B, que sorteia C, que sorteia...que sorteia A" , formando um 'loop'. 
Chamemos de 'cadeia' essa sequência de pessoas.


Então, seja V(n) o número de sorteios válidos com 'n' pessoas.

Quando acrescentamos a enésima-primeira pessoa a um grupo com 'n' pessoas, 
um sorteio válido qualquer corresponderá às seguintes situações:

a) essa pessoa forma uma cadeia com mais de 2 elementos.
b) essa pessoa forma uma cadeia com apenas 2 elementos (ela e uma 2a. pessoa 
fazem uma troca mútua de presentes).

No caso 'a', podemos considerar que essa pessoa é "inserida" em alguma das 
cadeias que haveria num sorteio válido com apenas 'n' pessoas.
No caso 'b' , cada sorteio pode ser obtido a partir da escolha do 2o. 
elemento, e então formando-se todos os sorteios válidos possíveis com (n-1) 
elementos.

Dessa forma, o número de sorteios válidos do tipo 'a' vale 'n*V(n)' .
Repare que essa nova pessoa pode ser inserida logo após uma pessoa qualquer 
dentre as 'n' existentes.

E o número de sorteios válidos do tipo'b' vale 'n*V(n-1)' .
Repare que essa nova pessoa pode fazer par com qualquer uma dentre as 'n' 
existentes, enquanto as outras (n-1) se organizam como um sorteio válido de 
(n-1) elementos.


Assim, V(n+1) = n*V(n) + n*V(n-1)
Fazendo V(n) = n! * W(n) , obtemos a equação de diferenças, linear e 
homogêna, do 1o grau:
[W(n+1) - W(n)]  +  1/(n+1) * [W(n) - W(n-1)]  = 0

Portanto, a solução geral é
W(n+1) - W(n) = C * (-1)^(n+1)/(n+1)!

Como V(1)=0 e V(2)=1 , então C=1 , pois W(1)=0 e W(2)=1/2 , que nos leva a
W(n+1) = W(n) + (-1)^(n+1)/(n+1)!

Como o número de sorteios possíveis é n! , a probabilidade de sorteios 
válidos com 'n' pessoas é P(n)= V(n)/n! .
Logo, P(n) = W(n) , ou seja,

P(n) = P(n-1) + (-1)^n/n! , onde P(1)=0

Além disso, é fácil verificar que quando 'n' cresce, P(n) converge para
P = 0 +1/2! - 1/3! + 1/4! ... = 1/e

[]'s,
Rogério.

_________________________________________________________________
MSN Hotmail, o maior webmail do Brasil.  http://www.hotmail.com

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