segunda-feira, 15 de dezembro de 2014

Amigo Invisível: Qual a Probabilidade de Dar Certo?

Fim de ano e é tradição do nosso país realizar amigo invisível. A brincadeira é tão simples quanto conhecida, por isso não vou entrar em detalhes. Algo frustrante, pelo menos no sorteio, é quando alguém sai com o próprio nome e, teoricamente, todos deveriam realizar o sorteio novamente para garantir o pretendido segredo (supostamente, com quem saímos deve ser surpresa para todos os outros). Uma pergunta natural parece ser:

Qual a probabilidade de que em um sorteio com n pessoas, ninguém tire o próprio nome?

Para facilitar, vamos inicialmente adotar um grupo de 10 pessoas, ou seja, n=10.

Em combinatória, quando uma fila é reorganizada de forma que nenhum elemento permaneça na mesma posição, dizemos que é uma permutação caótica (ou desarranjo). Pense nas 10 pessoas formando uma fila e cada uma delas com o papel com seu nome na mão. Em um sorteio de amigo invisível que deu certo, os papéis são trocados e vão todos para mãos diferentes. Em outras palavras, um sorteio de amigo invisível ótimo deve ser uma permutação caótica.

Felizmente, existe uma fórmula para calcular isso e está na página de desarranjo da Wikipedia. No caso de 10 pessoas, o número total de sorteios possível é 3.628.800 (10!, pelo Princípio Fundamental da Contagem). O número de sorteios ótimos, ou seja, o número de sorteios em que ninguém sai com seu próprio nome é de 1.334.961 (a fórmula do cálculo desse número encontra-se abaixo). Logo, a probabilidade de que em um sorteio com 10 pessoas ninguém saia com seu próprio nome é de

$\dfrac{1.334.961}{3.628.800}\approx 0.367879$

ou seja, aproximadamente 37% de chance de que o sorteio dê certo.

Abaixo, uma tabela de probabilidades. A linha de cima apresenta o número de pessoas envolvidas no Amigo Invisível e a de baixo a chance de que ninguém saia com o próprio nome.

Pessoas 0 1 2 3 4 5 6 7 8 9 10
Chance (%) 100 0 50 33.3333 37.5 36.6667 36.8056 36.7857 36.7881 36.7879 36.7879


ATENÇÃO, a parte abaixo é puramente matemática, mas sem muito rigor :)

Vamos calcular a probabilidade de um sorteio de amigo invisível com n pessoas ser ótimo, ótimo no sentido de ninguém sair com o próprio nome.

Temos que

$P=\dfrac{\#(E)}{\#(\Omega)}$

No caso, E é o conjunto dos sorteios ótimos, Ω o conjunto de todos os sorteios e #(A) é a cardinalidade do conjunto, ou seja, seu número de elementos. Pela referência (super confiável) da Wikipedia e pelo Princípio Fundamental da Contagem, temos que

$P=\dfrac{\displaystyle\sum_{k=0}^{n}(-1)^k\dfrac{n!}{k!}}{n!}$

$P=\displaystyle\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}$

$P=\dfrac{1}{0!}-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+\dfrac{1}{4!}-\dfrac{1}{5!}+\cdots+(-1)^n\dfrac{1}{n!}$


Se o número de pessoas for muito grande, exageradamente grande (maior do que qualquer número que você pensar), ou seja, fazendo n tender ao infinito, temos que.

$\displaystyle\lim_{n\rightarrow \infty} P=\displaystyle\lim_{n\rightarrow \infty} \displaystyle\sum_{k=0}^{n}\dfrac{(-1)^k}{k!}=e^{-1}$

A última parte pode ser percebida fazendo n=-1 na série de Taylor da função exponencial.

Logo, quanto maior o número de pessoas em um sorteio, mais próxima a probabilidade estará de 1/e = 0.36787944117144233 ≈ 36,7879 %.