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.