O Problema dos Encontros. Suponha que
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
?
Passo 1
O enunciado pede duas coisas claras:
- Calcular a probabilidade de que, numa devolução totalmente aleatória dos chapéus de
cavalheiros, pelo menos um cavalheiro receba o seu próprio chapéu. - Determinar o que acontece com essa probabilidade quando
.
Informações dadas e pressupostos:
- Há
chapéus e cavalheiros. - Todas as devoluções possíveis (permutations) são igualmente prováveis.
- O número total de maneiras de devolver os chapéus é
(fatorial de ). - 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
. Em fórmulas:
Portanto o foco passa a ser contar quantas permutações de
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
, o evento = “o cavalheiro recebe o seu próprio chapéu”. - Queremos o número de permutações em que nenhum dos
ocorre, isto é, o complemento da união . - Pelo princípio da inclusão-exclusão, o número de permutações em que nenhum
ocorre é
onde
é a soma, sobre todos os subconjuntos de
índices, do número de permutações que fixam precisamente esses
elementos (ou melhor: que fixam pelo menos esses
índices — a contagem padrão de inclusão-exclusão).
Agora calcule
:
- Para um subconjunto fixo de
indivíduos, se exigimos que esses recebam os seus próprios chapéus, então os restantes chapéus podem ser distribuídos livremente entre os restantes — isso dá permutações. - Existem
escolhas do subconjunto de indivíduos. Assim
Logo, pela fórmula de inclusão-exclusão:
Passo 4
Simplificação algébrica importante (para deixar a expressão mais elegante).
Observe que
Observe que
Substituindo na soma de
obtemos
Portanto a probabilidade de ninguém receber o próprio chapéu é
Passo 5
Concluir a probabilidade desejada (pelo menos um acerta):
Esta é uma fórmula exata, fechada e fácil de usar na prova: basta somar os termos até
.
Passo 6
Exemplos numéricos pequenos (para treinar e checar a intuição):
- Para
: , então . - Para
: , então . - Para
: , então .
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
cresce.
Passo 7
Limite quando
.
A soma que aparece na probabilidade de ninguém é a soma truncada da série de Taylor de avaliada em
:
A soma que aparece na probabilidade de ninguém é a soma truncada da série de Taylor de
Portanto, tomando
,
Logo
Numericamente,
. Vou usar a vírgula conforme preferes:
.
Passo 8
Intuição rápida e útil para a prova (sem formalidades pesadas):
- Para grande
, o número de pontos fixos em uma permutação aleatória converge em distribuição para uma Poisson com média . Para uma Poisson( ), a probabilidade de ter zero ocorrências é . Isso dá a mesma conclusão: probabilidade de nenhum é , de pelo menos um é . - 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
de que pelo menos um acerte.