Pendahuluan: Keajaiban Paling Kontraintuitif dalam Teori Probabilitas
Pada 2003, ilmuwan komputer Denmark Peter Bro Miltersen memperkenalkan teka-teki terkenal Masalah 100 Tahanan (100 Prisoners Problem):
- $100$ terpidana mati diberi nomor $1$ sampai $100$. Di sebuah ruangan terdapat $100$ kotak tertutup berisi kertas bernomor $1$ sampai $100$ yang dikocok secara acak (sebuah permutasi $\sigma \in S_{100}$).
- Aturan: Setiap tahanan masuk sendirian secara bergiliran dan boleh membuka paling banyak $50$ kotak untuk menemukan nomornya sendiri. Ruangan dikembalikan ke kondisi semula dan segala komunikasi dilarang setelah permainan dimulai (tetapi strategi boleh disepakati sebelumnya).
- Vonis: Hanya jika ke-$100$ tahanan semuanya menemukan nomor mereka, semuanya dibebaskan; jika satu orang saja gagal, ke-$100$ tahanan dieksekusi.
Jika setiap tahanan membuka $50$ kotak secara acak (strategi independen), peluang masing-masing adalah $1/2$, namun peluang selamat bersama menjadi:
$$\mathbb{P}(\text{semua selamat})_{\text{indep.}} = \left(\frac{1}{2}\right)^{100} \approx 7.89 \times 10^{-31}$$Namun, Sven Skyum menemukan Strategi Penelusuran Penunjuk (Pointer-Following Strategy) yang mendongkrak peluang selamat bersama menjadi $31.18\%$ tanpa mengirim satu bit informasi pun!
Bab 1: Penelusuran Penunjuk dan Dekomposisi Siklus Saling Lepas
Untuk tahanan bernomor $k \in \{1, \dots, 100\}$, strategi Skyum adalah:
- Langkah 1: Buka terlebih dahulu kotak No. $k$.
- Langkah 2: Jika kertas di dalamnya bernomor $x_1 = k$, berhasil; jika $x_1 \neq k$, selanjutnya buka kotak No. $x_1$.
- Langkah 3: Baca nomor $x_2$ dan buka kotak No. $x_2$, mengikuti rantai $k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots$ hingga menemukan $k$ atau menghabiskan $50$ kesempatan.
flowchart TD
Start["Tahanan k masuk ke ruangan (maks. 50 kesempatan)"]
Step1["Langkah 1: Buka kotak k, baca kertas x = σ(k)"]
Check{"Kertas x == k ?"}
Win["Nomor sendiri k ditemukan!"]
Limit{"Kotak dibuka < 50 ?"}
Next["Ikuti penunjuk: Buka kotak x (x ← σ(x))"]
Lose["Gagal dalam 50 langkah: Semua dieksekusi"]
Start --> Step1 --> Check
Check -- "Ya" --> Win
Check -- "Tidak" --> Limit
Limit -- "Ya" --> Next --> Check
Limit -- "Tidak (panjang siklus ℓ > 50)" --> Lose
Mengapa ini berhasil? Pemetaan kotak $\mapsto$ kertas adalah bijeksi $\sigma$ dalam grup simetris $S_{2n}$ ($2n=100$). Setiap permutasi hingga terurai secara tunggal menjadi siklus-siklus saling lepas (Disjoint Cycles):
$$\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100$$Karena $\sigma$ bijektif, berangkat dari kotak $k$, tahanan akan mengelilingi satu-satunya siklus tertutup yang memuat $k$ dan berakhir di $\sigma^{-1}(k)$ (kotak yang menyimpan kertas $k$). Maka:
- Tahanan $k$ berhasil dalam $\le 50$ langkah jika dan hanya jika siklusnya memiliki panjang $\ell \le 50$.
- Ke-$100$ tahanan selamat semuanya jika dan hanya jika permutasi $\sigma \in S_{100}$ tidak memiliki siklus dengan panjang $\ell > 50$!
Bab 2: Pencacahan Siklus Panjang dan Bilangan Harmonik ($1 - \ln 2$)
Untuk $2n$ tahanan ($n = 50$), sebuah permutasi $\sigma \in S_{2n}$ paling banyak memuat satu siklus dengan panjang $\ell > n$, sebab dua siklus lepas berukuran $> n$ membutuhkan minimal $2n+2 > 2n$ elemen. Jadi kejadian $E_\ell := \{\sigma \text{ memuat siklus sepanjang } \ell\}$ untuk $\ell = n+1, \dots, 2n$ saling lepas! Banyaknya permutasi di $E_\ell$ adalah:
- Memilih $\ell$ elemen siklus panjang: $\binom{2n}{\ell}$;
- Menyusunnya menjadi satu siklus melingkar: $(\ell - 1)!$;
- Mempermutasikan $2n - \ell$ elemen sisanya: $(2n - \ell)!$.
Perkaliannya menyederhanakan faktorial secara elegan:
$$|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}$$Dibagi $|S_{2n}| = (2n)!$, diperoleh $\mathbb{P}(E_\ell) = \frac{1}{\ell}$. Dengan bilangan harmonik $H_N = \sum_{k=1}^N \frac{1}{k}$, peluang selamat eksaknya adalah:
$$\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\%}$$Untuk $2n = 100$, kita peroleh $P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31.1828\%}$!
Bab 3: Penggandengan Risiko (Coupling) Tanpa Komunikasi
flowchart TD
Pool["Total risiko tetap: Ekspektasi gagal E[gagal] = 50"]
Indep["Strategi independen: Kegagalan tersebar di hampir semua semesta"]
Cycle["Strategi siklus: Nasib digandengkan pada struktur siklus σ"]
ResI["Minimal 1 gagal di 99.99...92% semesta → Selamat ≈ 7.89×10⁻³¹"]
ResC["Gagal dipadatkan di 68.82% (ℓ>50) → 31.18% semesta selamat 100%!"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| Karakteristik | 1. Strategi Independen | 2. Strategi Siklus |
|---|---|---|
| Peluang Individu $\mathbb{P}(A_k)$ | $50.00\%$ | $50.00\%$ (identik) |
| Ekspektasi Berhasil $\mathbb{E}[X]$ | $50$ tahanan | $50$ tahanan (identik) |
| Korelasi | Nol (independen) | Tergandeng kuat lewat $\sigma$ |
| Peluang $100$ Selamat | $(1/2)^{100} \approx 7.89 \times 10^{-31}$ | $1 - (H_{100} - H_{50}) \approx 31.18\%$ |
| Limit $n \to \infty$ | $0$ | $1 - \ln 2 \approx 30.685\%$ |
- Penggandengan (Coupling): Karena gagal 1 orang sama fatalnya dengan gagal 51 orang, strategi siklus memadatkan seluruh kegagalan ke dalam $68.82\%$ permutasi bersiklus $\ell > 50$, sehingga $31.18\%$ ruang sampel bersih tanpa satu pun kegagalan!
- Pertahanan terhadap Sipir Licik: Dengan menyepakati bijeksi acak rahasia $\tau \in S_{100}$ sebelumnya, konjugasi $\tau \sigma \tau^{-1}$ tetap menjamin peluang selamat $31.18\%$.