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
