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\%\).