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


4 comentários:

  1. lembra do exercício do hexágono?

    sentido positivo era sentido anti-horário.

    dai o exercício ficou ao contrário kkk
    bjs

    ResponderExcluir
    Respostas
    1. Aé. hehe, bom, mas eu falei lá né que não sabia o que era sentido positivo, hehehehe.
      Mas com o raciocínio lá fica mais tranquilo de fazer do outro jeito.

      Mas valeu.

      Excluir
  2. Resolução sensacional! Parabéns pelo site e, principalmente, pela iniciativa de ajudar os outros. Gente como você cresce exponencialmente ^.^
    RFF

    ResponderExcluir
  3. Valeu pelo elogio.
    Sempre que puder estarei ajudando.

    Abraço

    ResponderExcluir