Exercício Resolvido - Probabilidade de ninguém pegar seu próprio nome em um amigo secreto

Numa brincadeira de amigo secreto, qual a probabilidade de ninguém tirar o próprio nome quando o número de participantes tende ao infinito? 

Solução:

Este exercício parece ser simples mas é muito complicado.

Vou tentar explicar a forma como fiz o mais detalhado possível, porém o leitor deve estar bem atento a cada passo.

Inicialmente, vamos deduzir o universo de possibilidades.

Não é difícil perceber que o universo é de n! para n participantes, pois, o primeiro a sortear tem 'n' nomes para retirar. O segundo terá '(n-1)'. O terceiro, '(n-2)'... Logo, o número de possibilidades é:

n*(n-1)*(n-2)*...*1 = n!

Dessas possibilidades, vamos procurar quais são favoráveis, e da divisão das possibilidades favoráveis pelo número total temos a probabilidade.

Vou chamar de Prob(n) = [P(n) / n!] a probabilidade solicitada. Ou seja, P(n) é o número de possibilidades favoráveis

Vamos lá. Um estudo específico rápido:

Se fosse 1 participante, a probabilidade seria 0%.

Se fossem 2, teríamos que o 1º não poderia pegar seu nome. Como o universo de possibilidades é 2 e apenas uma delas satisfaz, e probabilidade aqui seria 1/2 = 0,5

Se fossem 3, temos que pensar da seguinte forma para saber o universo de possibilidades:

Se o primeiro tirar seu nome, já não nos serve mais. Como este caso tem 2 possibilidades (a de o segundo e o terceiro também tirarem seus nomes, e a de o 2° tirar o nome do 3° e o 3° tirar o do 2°), resta verificar os outros casos;

Se o 1° tirar o nome do 2°:

Pode o 2° tirar o do 1° e o 3° o dele mesmo -> não serve;

Pode o 2° tirar o do 3° e o 3° o do 1° -> OK

Se o 1° tirar o do 3°, ocorre o mesmo, ou seja, das 2 possibilidades, onde uma é válida.

Assim, neste caso (3 participantes), o universo de possibilidades é 3*2*1 = 6, e as válidas são 2. Temos 2/6 = 1/3 a probabilidade.

Perceba que existem dois casos. Um é o primeiro pegar o seu próprio nome. E este não nos serve. O outro é ele pegar o nome de outro participante. Assim, restará o nome dele e de mais um. Supondo que o participante que o primeiro pegou o nome, pegar o nome do primeiro (ou seja, um pega o nome do outro), resta a situação de apenas um participante, ou seja, o participante que não sorteou só poderá pegar o próprio nome, que é o caso de se só existisse um participante.

Vamos analisar como seria com 4 participantes, o pensamento é análogo ao se fossem 3:

Se o 1° tirar seu nome, os outros casos não nos serve. Ou seja, temos 3! = 6 possibilidades que não servem.

Se o 1° tirar o nome do 2°:

O 2° tira o do 1° o 3° tira o próprio e o 4° o próprio -> Não serve

O 2º tira o do 1°, o 3° o do 4° o 4° o do 3º -> OK

O 2° tira o do 3°, o 3° o do 1º o 4º o próprio -> não serve

O 2° tira o do 3°, o 3° o do 4º, o 4º o do 1º -> OK

O 2° tira o do 4°, o 3º o próprio, o 4° o do 1º -> Não serve

O 2° tira o do 4º, o 3º o do 1º, o 4º o do 3° -> Ok

Total de 3 possibilidades neste caso.

Como o 1º pode ainda tirar o do 3° e do 4°, e nesses casos teremos a mesma situação acima (3 favoráveis em cada), são 9 as possibilidades satisfatórias. 9/24 = 3/8.

Mais uma vez, o que foi observado no caso de 3 participantes, ocorreu. Veja que aqui existe também a possibilidade do 1º tirar o seu próprio nome (que não serve) e de ele tirar o nome que outro participante. Como são 4 participantes, as possibilidades do 1º tirar o nome de outro são 3. Digamos que ele pegue o nome de outro participante, chamado de B. Neste caso, se o participante B tirar o nome do 1º, vão restar 2 nomes e dois participantes. Porém, como no caso de existirem apenas 2 no jogo do amigo secreto, os dois participantes que restaram tem os seus nomes a serem sorteados. Caso o B não pegue o nome do 1º, e pegue o nome de um jogador C. Segue a lógica: se o C pegar o nome do 1º, resta um jogador e um nome (caso do jogo de apenas um participante, já que o nome que sobrou é exatamente o nome do jogador que não sorteou), se ele pegar o nome de um participante D ...

Agora, vou fazer o mesmo que fiz acima, porém de forma genérica, para n participantes.

Já foi visto que o universo de possibilidades é de n!.

Neste caso, para n participantes, temos:

Se o 1° pegar seu nome. já não serve mais -> (n-1)! casos descartados

Se o 1º pegar o nome de outro participante (participante X) [ (n-1) possibilidades ]

Se X pegar o nome do 1º (1 possibilidade) restam (n-2) participantes com seus próprios (n-2) nomes. Neste caso, a probabilidade dos casos favoráveis será P(n-2), já que os nomes não sorteados são exatamente o dos participantes que restaram.

Mas se X pegar o nome de um terceiro (Y) (n-2 possibilidades) obtém-se os mesmos 2 casos:

Y pegar o nome do 1º (1 possibilidade), restando (n-3) participantes e seus (n-3) nomes. P(n-3)

Y pegar outro (Z) (n-3 possibilidades):

Z pegar o nome do 1º (1 possibilidade): P(n-4)

.......

E assim vai.

Assim, teremos que:

P(n) = (n-1)*[P(n-2) + (n-2)*[P(n-3) + (n-3)*[P(n-4) + (n-4)*[P(n-5) + ... + 3*[P(2) + 2*[P(1)]]]...]]]

Da igualdade acima, temos:

P(n-1) = (n-2)*[P(n-3) + (n-3)*[P(n-4) + ... + 2*[P(1)]]]...]]]

Assim:

P(n) = (n-1)*[P(n-2) + P(n-1)]

Lembrando que a probabilidade é Prob(n) = P(n) / n!

A relação P(n) = (n-1)*[ P(n-1) + P(n-2) ] estabelece uma relação de subfatorial.

Assim, dividindo tudo por n! (universo) temos:

(Aconselho ao leitor a acompanhar com um papel e um lápis a partir daqui)

P(n)/n! = (n-1)*{ P(n-1) + P(n-2)] } / n!

P(n)/n! = [(n-1)/n]*{ P(n-1)/(n-1)! + P(n-2)/(n-1)!] }

P(n)/n! = [(n-1)/n]*{ P(n-1)/(n-1)! + [1/(n-1)]*[P(n-2) /(n-2)!] }

Desta forma temos:

Prob(n) = [(n-1)/n]*{ Prob(n-1) + [1/(n-1)]*Prob(n-2) }

Prob(n) = (1 - 1/n )*{ Prob(n-1) + [1/(n-1)]*Prob(n-2) }

Prob(n) = Prob(n-1) - (1/n)*Prob(n-1) + [1/(n-1)]*Prob(n-2) - (1/n)*[1/(n-1)]*Prob(n-2) ]

Prob(n) = Prob(n-1) - (1/n)*Prob(n-1) + [(n-1)/n]*[1/(n-1)]*Prob(n-2) ]

Prob(n) = Prob(n-1) - (1/n)*Prob(n-1) + (1/n)*Prob(n-2) ] 

Prob(n) - Prob(n-1) = - (1/n)*Prob(n-1) + [1/n]*[ Prob(n-2) ]

Prob(n) - Prob(n-1) = (-1/n)* [ Prob(n-1) - Prob(n-2) ]

Seja G(n) = Prob(n) - Prob(n-1)

G(n) = (-1/n) G(n-1)

Como:

G(2) = Prob(2) - Prob(1) = 1/2 - 0 = 1/2

G(3) = (-1/3)*(1/2) = -1/6

G(4) = (-1/4)*(1/6) = 1/24

...

G(k) = [(-1)^k] / k!

Assim:

Prob(n) = Prob(1) + [Prob(2) - Prob(1)] + [Prob(3) - Prob(2)] + ... + [Prob(n) - Prob(n-1)]

Prob(n) = 0 + G(2) + G(3) + G(4) + ... + G(n)

Prob(n) = Ʃ{ [(-1)^k] / k! }

Mas, da série de Taylor temos que:

e^x = Ʃ[ ( x^k ) / k! ], se tivermos x = -1, a série será:

e^(-1) = Ʃ{ [ (-1)^k ] / k! } = Prob(n) para n tendendo ao infinito

Logo, Prob(n) = 1/e