Vinte e três pessoas bastam

A pergunta

Uma sala, e pessoas entrando uma por uma. A cada pessoa que entra, a mesma pergunta: já existem duas aqui dentro que fazem aniversário no mesmo dia? O ano tem 365 dias. Quantas pessoas precisam entrar para que a coincidência fique mais provável do que improvável?

O palpite mais comum fica perto da metade do ano — 180, 150 — e há quem diga que só com uns trezentos e poucos dá para ter segurança. A resposta é 23. Com 23 pessoas a chance de duas compartilharem o aniversário já é de 50,73%. Com 60 pessoas, 99,4%. Com 70, 99,92%.

Vinte e três é uma sala de aula pequena, um time de futebol com os reservas e o técnico. O número parece impossível — e o motivo de parecer impossível é a parte mais interessante do problema.

Conte pares, não pessoas

O erro não está na conta: está na pergunta que a cabeça ouviu. “Duas pessoas no mesmo dia” não tem ninguém no centro. Serve qualquer par. Então conte o que a pergunta conta: pares de pessoas.

A primeira pessoa forma par com as outras 22. A segunda, com 21 que ainda não foram contadas. A terceira, com 20. Somando tudo:

$$22+21+20+\cdots +1=\frac{22\cdot 23}{2}=253\text{pares}.$$

Em geral, numa sala de $n$ pessoas, o número de pares é

$$\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}.$$

(Essa soma tem uma prova que cabe num desenho: duas escadas iguais se encaixam num retângulo. Ela está nas provas sem palavras.)

O que importa é a velocidade. Pessoas crescem em linha reta; pares crescem com o quadrado. Dobre a sala de 23 para 46 e o número de pares não dobra: vai de 253 para 1.035, quatro vezes mais.

A conta, pelo avesso

Calcular “pelo menos duas coincidem” diretamente é horrível: pode ser um par, dois pares, um trio, um par e um trio… Calcular o contrário — “ninguém coincide com ninguém” — é fácil, e a resposta é tudo o que sobra.

A primeira pessoa entra e pode nascer em qualquer dia. A segunda precisa evitar um dia: chance $\frac{364}{365}$. A terceira precisa evitar dois: $\frac{363}{365}$. A $k$-ésima precisa evitar $k-1$ dias. Como os aniversários são independentes, as chances se multiplicam:

$$\begin{array}{rl}P(\text{todos diferentes})& =\frac{365}{365}\cdot \frac{364}{365}\cdot \frac{363}{365}\cdots \frac{365-n+1}{365}\\ & =\prod _{k=0}^{n-1}\left(1-\frac{k}{365}\right).\end{array}$$

Cada fração é quase 1. Mas com 23 pessoas são 22 frações multiplicadas, e “quase 1” multiplicado 22 vezes desaba:

$$\begin{array}{rl}P(\text{todos diferentes})& =\frac{365!}{342!365^{23}}\approx 0,4927,\\ P(\text{alguma coincideˆncia})& =1-0,4927\approx 0,5073.\end{array}$$

Repare na linha de 57 pessoas: a chance já passa de 99%. E em nenhum momento a tabela precisou de 366 pessoas — que é o único número que garante uma coincidência (pelo princípio da casa dos pombos).

De onde vem a raiz quadrada

A tabela não explica por que 23. A aproximação explica. Para $x$ pequeno, $1-x\approx e^{-x}$; aplicando a cada fator do produto,

$$\prod _{k=0}^{n-1}\left(1-\frac{k}{N}\right)\approx \exp \left(-\sum _{k=0}^{n-1}\frac{k}{N}\right)=\exp \left(-\frac{n(n-1)}{2N}\right).$$

Olhe o expoente: é o número de pares dividido por $N$. A chance de ninguém coincidir é como se cada um dos $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pares tivesse, sozinho, chance $1/N$ de coincidir, e todos fossem independentes. Igualando a ½:

$$\frac{n(n-1)}{2N}=\ln 2⟹n\approx \sqrt{2N\ln 2}\approx 1,1774\sqrt{N}.$$

Para $N=365$, $\sqrt{365}\approx 19,1$ e $n\approx$ 23,0. A sala precisa crescer com a raiz quadrada do número de dias, e não com o número de dias. É essa raiz que a intuição não enxerga.

A intuição não é burra: é egocêntrica

Quando alguém diz “duas pessoas no mesmo dia”, a gente se imagina na sala procurando quem faça aniversário no nosso dia. Essa é outra pergunta, e para ela 23 é pouco mesmo. A chance de pelo menos uma entre $m$ outras pessoas nascer no seu dia é

$$P(\text{algueˊm no meu dia})=1-{\left(\frac{364}{365}\right)}^m,$$

e ela só passa de 50% com $m=$ 253 outras pessoas. A conta é honesta; a pergunta é que era outra. “Alguém no meu dia” olha 22 pares, todos passando por você. “Duas pessoas quaisquer” olha 253 — onze vezes e meia mais chances, na mesma sala.

Onde isso aparece de verdade

Todo sistema que gera códigos que deveriam ser únicos vive esse problema.

Hashes curtos. O Git identifica cada versão do código por um hash enorme e, por padrão, mostra só os sete primeiros dígitos hexadecimais. São $16^7=$ 268.435.456 possibilidades. Pela mesma raiz quadrada, a chance de dois desses códigos curtos coincidirem chega a 50% com cerca de 19.291 versões — em repositórios grandes isso acontece de fato, e é por isso que o Git estica a abreviação quando precisa.

O ataque do aniversário. Uma assinatura digital de $b$ bits tem $2^b$ valores possíveis. Para achar uma mensagem com a assinatura de outra específica, você precisa de uns $2^b$ chutes — é a pergunta “alguém no meu dia”. Para achar duas mensagens quaisquer com a mesma assinatura, bastam uns $\sqrt{2^b}=2^{b/2}$:

$$n_{50\%}\approx 1,1774\sqrt{2^b}\approx 2^{b/2}.$$

Por isso uma assinatura de 128 bits resiste a colisões como se tivesse 64 — metade da força, de graça, só porque servem duas quaisquer. É o motivo de funções de hash modernas usarem 256 bits ou mais.

Identificadores aleatórios. Um UUID versão 4 tem 122 bits sorteados. A chance de colisão chega a 50% só depois de uns $1,1774\cdot 2^{61}\approx 2,7\times 10^{18}$ identificadores — gerando um bilhão por segundo, seriam uns 86 anos. Aqui a raiz quadrada trabalha a favor.

Variações

Três pessoas no mesmo dia. Exigir um trio muda tudo: a sala precisa de 88 pessoas para passar de 50% (com 88, a chance é 51,1%). A conta exata soma as salas em que nenhum dia tem mais de duas pessoas:

$$P(\text{nenhum trio})=\sum _k\frac{365!}{k!(n-2k)!(365-n+k)!}\cdot \frac{n!}{2^k}\cdot \frac{1}{365^n}.$$

Aniversários vizinhos. Se contar como coincidência nascer no mesmo dia ou em dias consecutivos, bastam 14 pessoas (53,7% com 14).

Anos desiguais. Na vida real os nascimentos não se distribuem por igual: há meses mais cheios que outros. Isso só aumenta a chance de coincidência — a distribuição uniforme é o pior caso, e as contas acima são um piso.

A primeira coincidência. Se as pessoas entram uma por uma, a primeira coincidência chega, em média, na 24,62ª pessoa. A distribuição completa aparece na vista Mil salas do laboratório.

Os números do episódio

Desafios

Para ir além

• O problema costuma ser atribuído a Richard von Mises, que o publicou em 1939. As contas exatas de trios e de aniversários vizinhos são clássicas da literatura de probabilidade.
• O mesmo raciocínio de pares aparece no problema da parada ótima e em qualquer pergunta sobre coincidências: antes de calcular, pergunte se ela é sobre você ou sobre dois quaisquer.
• No laboratório, as quatro vistas desta página aparecem juntas, com controles completos.