Introdução: O milagre mais contraintuitivo da probabilidade
Em 2003, o cientista da computação dinamarquês Peter Bro Miltersen apresentou o famoso problema dos 100 prisioneiros:
- $100$ condenados à morte são numerados de $1$ a $100$. Em uma sala há $100$ caixas fechadas contendo os números de $1$ a $100$ embaralhados aleatoriamente (uma permutação $\sigma \in S_{100}$).
- Regra: Cada prisioneiro entra sozinho por vez e pode abrir no máximo $50$ caixas procurando seu próprio número. Ao sair, a sala é deixada exatamente como estava e toda comunicação é proibida após o início (mas uma estratégia pode ser combinada antes).
- Condição de sobrevivência: Somente se todos os $100$ prisioneiros encontrarem seu número todos são libertados; se um único falhar, todos os $100$ são executados.
Se cada prisioneiro abrir $50$ caixas ao acaso (estratégia independente), cada um tem chance $1/2$, mas a sobrevivência coletiva cai para:
$$\mathbb{P}(\text{todos sobrevivem})_{\text{indep.}} = \left(\frac{1}{2}\right)^{100} \approx 7.89 \times 10^{-31}$$Contudo, Sven Skyum descobriu a estratégia de rastreamento de ponteiros (Pointer-Following Strategy), que eleva a sobrevivência coletiva para $31.18\%$ sem transmitir um único bit de informação!
Capítulo 1: Rastreamento de ponteiros e decomposição em ciclos disjuntos
Para o prisioneiro número $k \in \{1, \dots, 100\}$, a estratégia de Skyum consiste em:
- Passo 1: Abrir primeiro a caixa n.º $k$.
- Passo 2: Se o bilhete interno mostrar $x_1 = k$, sucesso; se $x_1 \neq k$, abrir em seguida a caixa n.º $x_1$.
- Passo 3: Ler o número $x_2$ e abrir a caixa n.º $x_2$, seguindo a cadeia $k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots$ até achar $k$ ou esgotar as $50$ tentativas.
flowchart TD
Start["O prisioneiro k entra na sala (máx. 50 tentativas)"]
Step1["Passo 1: Abrir a caixa k, ler o bilhete x = σ(k)"]
Check{"Bilhete x == k ?"}
Win["Número próprio k encontrado!"]
Limit{"Caixas abertas < 50 ?"}
Next["Seguir o ponteiro: Abrir a caixa x (x ← σ(x))"]
Lose["Não encontrado em 50 passos: Execução de todos"]
Start --> Step1 --> Check
Check -- "Sim" --> Win
Check -- "Não" --> Limit
Limit -- "Sim" --> Next --> Check
Limit -- "Não (comprimento do ciclo ℓ > 50)" --> Lose
Por que funciona? O mapeamento caixa $\mapsto$ bilhete é uma bijeção $\sigma$ do grupo simétrico $S_{2n}$ ($2n=100$). Toda permutação finita decompõe-se de forma única em ciclos disjuntos:
$$\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100$$Como $\sigma$ é bijetiva, partindo da caixa $k$ o prisioneiro percorre o único ciclo fechado que contém $k$ e termina em $\sigma^{-1}(k)$ (a caixa que guarda o bilhete $k$). Portanto:
- O prisioneiro $k$ tem sucesso em $\le 50$ passos se e somente se seu ciclo tiver comprimento $\ell \le 50$.
- Os $100$ prisioneiros sobrevivem todos se e somente se a permutação $\sigma \in S_{100}$ não contiver nenhum ciclo de comprimento $\ell > 50$!
Capítulo 2: Contagem de ciclos longos e números harmônicos ($1 - \ln 2$)
Para $2n$ prisioneiros ($n = 50$), uma permutação $\sigma \in S_{2n}$ pode ter no máximo um único ciclo de comprimento $\ell > n$, pois dois ciclos disjuntos de comprimento $> n$ somariam pelo menos $2n+2 > 2n$ elementos. Assim, os eventos $E_\ell := \{\sigma \text{ contém um ciclo de comprimento } \ell\}$ para $\ell = n+1, \dots, 2n$ são mutuamente exclusivos. O número de permutações em $E_\ell$ é:
- Escolher os $\ell$ elementos do ciclo longo: $\binom{2n}{\ell}$;
- Ordená-los em um único ciclo circular: $(\ell - 1)!$;
- Permutar os $2n - \ell$ elementos restantes: $(2n - \ell)!$.
Multiplicando, os fatoriais se cancelam:
$$|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}$$Dividindo por $|S_{2n}| = (2n)!$, temos $\mathbb{P}(E_\ell) = \frac{1}{\ell}$. Usando os números harmônicos $H_N = \sum_{k=1}^N \frac{1}{k}$, a probabilidade exata de sobrevivência é:
$$\boxed{P_{\text{success}}(2n) = 1 - \sum_{\ell = n+1}^{2n} \frac{1}{\ell} = 1 - \left(H_{2n} - H_n\right) \xrightarrow{n \to \infty} 1 - \int_1^2 \frac{dx}{x} = 1 - \ln 2 \approx 30.685\%}$$Para $2n = 100$, obtemos $P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31.1828\%}$.
Capítulo 3: Acoplamento de riscos sem transmissão de informação
flowchart TD
Pool["Risco total fixo: Esperança de falhas E[falhas] = 50"]
Indep["Estratégia independente: Falhas dispersas em quase todos os universos"]
Cycle["Seguimento de ciclos: Destinos acoplados à estrutura cíclica de σ"]
ResI["Pelo menos 1 falha em 99.99...92% dos universos → Sobrevivência ≈ 7.89×10⁻³¹"]
ResC["Falhas concentradas em 68.82% (ℓ>50) → 31.18% de universos com 100% de sucesso!"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| Característica | 1. Estratégia independente | 2. Estratégia de ciclos |
|---|---|---|
| Sucesso individual $\mathbb{P}(A_k)$ | $50.00\%$ | $50.00\%$ (idêntico) |
| Esperança de sucessos $\mathbb{E}[X]$ | $50$ prisioneiros | $50$ prisioneiros (idêntico) |
| Correlação | Nula (independente) | Fortemente acoplada via $\sigma$ |
| Sobrevivência dos $100$ | $(1/2)^{100} \approx 7.89 \times 10^{-31}$ | $1 - (H_{100} - H_{50}) \approx 31.18\%$ |
| Limite $n \to \infty$ | $0$ | $1 - \ln 2 \approx 30.685\%$ |
- Acoplamento (Coupling): Como 1 falha ou 51 falhas produzem a mesma condenação, a estratégia de ciclos concentra todas as falhas nos $68.82\%$ de permutações com um ciclo $\ell > 50$, liberando $31.18\%$ do espaço amostral com zero falhas!
- Defesa contra um diretor malicioso: Combinando antes uma bijeção aleatória secreta $\tau \in S_{100}$, a conjugação $\tau \sigma \tau^{-1}$ garante exatamente os $31.18\%$ de sobrevivência.