Re: [obm-l] Amigo secreto...

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

On Thu, Dec 05, 2002 at 09:26:19AM -0200, Eduardo Azevedo wrote:
> É verdade que o jeito comum, só tem e^-1 de chance de nao "dar certo", mas
> ai e so tirar outro papelzinho.
> A pior coisa desse método são os ciclos pequenos (que quase sempre
> acontecem).

Depende do que você considera "quase sempre"...

Com o sorteio simples que você sugere e um grupo de n pessoas,
a probabilidade de obtermos um único ciclo é 1/n.
A probabilidade de obtermos exatamente dois ciclos (de qualquer
tamanho) é significativamente maior: H(n-1)/n.
Estou usando a notação

H(k) = 1 + 1/2 + 1/3 + ... + 1/k ~= log k

onde este log é na base e (log na base 10 é uma destas coisas
totalmente obsoletas que só sobrevivem em livros escolares).
Talvez seja interessante estudar a probablilidade de todos
os ciclos terem tamanho pelo menos m em um sorteio com n pessoas.

[]s, N.

=========================================================================
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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================