O Problema dos Encontros. Suponha que n cavalheiros deixem seus chapéus na chapelaria de um restaurante. Na saída, o recepcionista, que está embriagado, devolve os chapéus de forma totalmente aleatória. Qual é a probabilidade de que pelo menos um cavalheiro receba o seu próprio chapéu? O que acontece com essa probabilidade quando n \rightarrow \infty ?

Passo 1

O enunciado pede duas coisas claras:
  • Calcular a probabilidade de que, numa devolução totalmente aleatória dos chapéus de n cavalheiros, pelo menos um cavalheiro receba o seu próprio chapéu.
  • Determinar o que acontece com essa probabilidade quando n \rightarrow \infty.
Informações dadas e pressupostos:
  • n chapéus e n cavalheiros.
  • Todas as devoluções possíveis (permutations) são igualmente prováveis.
  • O número total de maneiras de devolver os chapéus é n! (fatorial de n).
  • Vamos denotar por um evento “ninguém recebe o seu próprio chapéu” — esse número de permutações especiais é o que precisamos contar para obter probabilidades.

Passo 2

Estratégia básica (sem fazer contas ainda): é mais fácil calcular primeiro a probabilidade do evento complementar “ninguém recebe o seu chapéu” e depois subtrair de 1. Em fórmulas:
\Pr(\text{pelo menos um recebe o próprio chapéu}) = 1 - \Pr(\text{ninguém recebe o próprio chapéu}).óééóé
Portanto o foco passa a ser contar quantas permutações de n elementos não têm pontos fixos (isto é, nenhum elemento fica na sua posição original). Essas permutações sem pontos fixos são chamadas de derangements; vamos contar quantas são.

Passo 3

Contagem por inclusão-exclusão (explicada passo a passo).
  • Definimos, para i=1,\dots,n, o evento A_i = “o cavalheiro i recebe o seu próprio chapéu”.
  • Queremos o número de permutações em que nenhum dos A_i ocorre, isto é, o complemento da união \bigcup_{i=1}^n A_i.
  • Pelo princípio da inclusão-exclusão, o número de permutações em que nenhum A_i ocorre é
D_n = \sum_{k=0}^{n} (-1)^k \cdot S_k,
onde S_k é a soma, sobre todos os subconjuntos de k índices, do número de permutações que fixam precisamente esses k elementos (ou melhor: que fixam pelo menos esses k índices — a contagem padrão de inclusão-exclusão).
Agora calcule S_k:
  • Para um subconjunto fixo de k indivíduos, se exigimos que esses k recebam os seus próprios chapéus, então os restantes n-k chapéus podem ser distribuídos livremente entre os n-k restantes — isso dá (n-k)! permutações.
  • Existem \binom{n}{k} escolhas do subconjunto de k indivíduos. Assim
S_k = \binom{n}{k} (n-k)!.
Logo, pela fórmula de inclusão-exclusão:
D_n = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)!.

Passo 4

Simplificação algébrica importante (para deixar a expressão mais elegante).
Observe que
\binom{n}{k} (n-k)! = \frac{n!}{k!(n-k)!} (n-k)! = \frac{n!}{k!}.
Substituindo na soma de D_n obtemos
D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.
Portanto a probabilidade de ninguém receber o próprio chapéu é
\Pr(\text{ninguém}) = \frac{D_n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!}.é

Passo 5

Concluir a probabilidade desejada (pelo menos um acerta):
\Pr(\text{pelo menos um}) = 1 - \Pr(\text{ninguém}) = 1 - \sum_{k=0}^{n} \frac{(-1)^k}{k!}.é
Esta é uma fórmula exata, fechada e fácil de usar na prova: basta somar os termos até k=n.

Passo 6

Exemplos numéricos pequenos (para treinar e checar a intuição):
  • Para n=1: \Pr(\text{ninguém})=\sum_{k=0}^{1}\frac{(-1)^k}{k!}=1-1=0é, então \Pr(\text{pelo menos um})=1.
  • Para n=2: \Pr(\text{ninguém})=1-1+\tfrac{1}{2}= \tfrac{1}{2}é, então \Pr(\text{pelo menos um})=\tfrac{1}{2}.
  • Para n=3: \Pr(\text{ninguém})=1-1+\tfrac{1}{2}-\tfrac{1}{6}=\tfrac{1}{3}é, então \Pr(\text{pelo menos um})=\tfrac{2}{3}.
Esses exemplos mostram que a probabilidade de “pelo menos um” não é nem 0 nem 1 para valores pequenos; ela tende a um certo valor limite quando n cresce.

Passo 7

Limite quando n \rightarrow \infty.
A soma que aparece na probabilidade de ninguém é a soma truncada da série de Taylor de e^{x} avaliada em x=-1:
e^{-1} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}.
Portanto, tomando n\to\infty,
\lim_{n\to\infty} \Pr(\text{ninguém}) = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!} = e^{-1}.é
Logo
\lim_{n\to\infty} \Pr(\text{pelo menos um}) = 1 - e^{-1}.
Numericamente, 1 - e^{-1} \approx 1 - 0,3678794412 = 0,6321205588. Vou usar a vírgula conforme preferes: 0,6321205588.

Passo 8

Intuição rápida e útil para a prova (sem formalidades pesadas):
  • Para grande n, o número de pontos fixos em uma permutação aleatória converge em distribuição para uma Poisson com média 1. Para uma Poisson( 1), a probabilidade de ter zero ocorrências é e^{-1}. Isso dá a mesma conclusão: probabilidade de nenhum é e^{-1}, de pelo menos um é 1-e^{-1}.
  • Então, mesmo que pareça que com muitas pessoas a chance de alguém receber o próprio chapéu seria muito alta ou muito baixa, ela converge para cerca de 63,2\% de que pelo menos um acerte.

Resposta

\Pr(\text{pelo menos um}) = 1 - \displaystyle\sum_{k=0}^{n} \frac{(-1)^k}{k!}
\displaystyle\lim_{n\to\infty}\Pr(\text{pelo menos um}) = 1 - e^{-1} \approx 0,6321205588

Exercícios relacionados