100 Mahkum Problemi: "İmkânsız" Görünen Bir Şansı %30'a Çıkaran Hile

Garip bir hapishane oyunu hayal edin. Müdür 100 mahkumu çağırır ve şu kuralları açıklar:

Bir odada 100 numaralandırılmış kutu var. Her kutunun içinde, rastgele yerleştirilmiş bir mahkumun adı bulunuyor. Tek tek odaya gireceksiniz; sıranızda en fazla 50 kutuyu açabilirsiniz. Açtığınız kutuların içine bakabilirsiniz ama kutuları yerinde bırakmak zorundasınız (sonradan giren mahkum her şeyi başlangıçtaki haliyle bulmalı). İçinizden her biri kendi adını bulursa — yani 100 mahkumun 100'ü de başarırsa — hepiniz serbestsiniz. Eğer tek bir mahkum bile başarısız olursa, hepiniz ölürsünüz.

Oyun başlamadan önce strateji konuşabilirsiniz. Ama oyun başladıktan sonra mahkumlar arasında iletişim yok.

İlk sezgi inanılmaz karamsardır. Bir tek mahkumun rastgele 50 kutuyu seçip içinde kendi adını bulma olasılığı $\tfrac{50}{100} = \tfrac{1}{2}$. 100 mahkumun hepsinin rastgele başarması olasılığı ise:

$\left(\frac{1}{2}\right)^{100} \approx 8 \times 10^{-31}$

Yani evrenin yaşı kadar oyun oynasanız bir kez bile kazanamazsınız. Üstelik biraz strateji konuşmuş olsanız bile durum görünüşte çok zor — çünkü mahkumlar oyun başlayınca iletişim kuramıyor.

Ama matematikçiler 2003'te şaşırtıcı bir cevap buldu: doğru stratejiyle hayatta kalma olasılığı %30'un üzerine çıkıyor. Bu sonuç ilk duyulduğunda "imkânsız" gibi gelir. Nasıl?

Döngü stratejisi

Strateji şudur. Tüm kutular önceden $1, 2, 3, \ldots, 100$ olarak numaralandırılmış olsun; her mahkum da bir numara taşısın ($1$'den $100$'e). Her mahkum şu yolu izlesin:

1. Önce kendi numarasına sahip kutuyu aç.
2. Açtığın kutunun içinde bir isim göreceksin. O ismin sahibinin numarasına sahip kutuyu aç.
3. Bu kutunun içinde de bir isim göreceksin. Yine o ismin sahibinin numarasına git.
4. Bu şekilde adımı bulana kadar (ya da 50 deneme bitene kadar) devam et.

Yani her mahkum, kendi numarasından başlayan bir zincir takip ediyor. Zincirin sonunda kendi adı gelirse o mahkum kazanır.

Bu kural, görünüşte rastgele bir gezintiden hiçbir farklı değil. Ama matematiksel olarak çok güçlü bir özelliğe sahip: her mahkumun gezisi, kutuların başlangıç dağılımındaki bir permütasyon döngüsünün uzunluğuna eşittir.

Permütasyonların döngüleri

100 kutuya 100 ismi yerleştirme işi, $1\ldots100$ üzerindeki bir permütasyon olarak görülebilir. Her permütasyon, ayrık döngülere ayrılır.

Örnek: $5$ kutu olduğunu düşünün. Kutuların içindeki isimler şöyle olsun:

• Kutu 1 → Ad 3
• Kutu 3 → Ad 5
• Kutu 5 → Ad 1
• Kutu 2 → Ad 4
• Kutu 4 → Ad 2

Burada iki döngü vardır: $(1 \to 3 \to 5 \to 1)$, uzunluğu 3. Ve $(2 \to 4 \to 2)$, uzunluğu 2.

Mahkum stratejisini uyguladığında: numarası $1$ olan mahkum kutu $1$'i açar, ad "3" bulur; kutu $3$'ü açar, ad "5" bulur; kutu $5$'i açar — ve kendi adı "1"i bulur. Yani 3 denemede bulur. Aynı şekilde 3 numaralı ve 5 numaralı mahkumlar da bu döngünün üyesi olduğundan en fazla 3 deneme yapar ve başarılı olur.

Kritik gözlem: Her mahkum, içinde bulunduğu döngüyü baştan sona izler. Eğer döngünün uzunluğu 50 ya da daha kısaysa, o döngünün her üyesi başarılı olur. Döngü 51 ya da daha uzunsa, o döngüdeki tüm mahkumlar 50 deneme içinde adlarını bulamaz.

Hepimiz mi kazandık?

İşte stratejinin gücü: hepsi birden başarısız olmak için tek bir döngünün uzunluğunun 50'yi geçmesi yeter. Yani tüm mahkumlar şu duruma indirgenir:

"Permütasyondaki en uzun döngünün uzunluğu $\le 50$ mi?" Eğer evet, hepsi kazanır. Eğer hayır, hepsi kaybeder.

Şimdi matematik soru çok netleşti. Rastgele bir permütasyonda en uzun döngünün $\le 50$ olma olasılığı nedir?

Cevap, kombinatorikten gelir. Bir $2n$ uzunluklu permütasyonda en uzun döngünün $> n$ olma olasılığı şuna eşittir:

$P(\text{en uzun döngü} > n) = \sum_{k=n+1}^{2n} \frac{1}{k} = H_{2n} - H_n$

Burada $H_m = 1 + \tfrac{1}{2} + \tfrac{1}{3} + \cdots + \tfrac{1}{m}$ harmonik sayıdır.

$n = 50$ için $H_{100} - H_{50} \approx \ln(100) - \ln(50) = \ln 2 \approx 0{,}693$. Dolayısıyla en uzun döngünün 50'yi aşma olasılığı yaklaşık %69. Tersi: hayatta kalma olasılığı yaklaşık $1 - 0{,}693 = 0{,}307$, yani %30,7.

Daha büyük $n$ değerleri için olasılık asla %30'un (daha doğrusu $1 - \ln 2 \approx 0{,}3069$) altına düşmez.

Karşılaştırın: rastgele strateji $\approx 10^{-30}$ verirken; döngü stratejisi $\approx 0{,}307$. Bu, matematik tarihinde "stratejinin gücünün" en açık örneklerinden biridir.

Bu nasıl mümkün?

İlk başta paradoks gibi geliyor. Her mahkumun tek başına stratejinin verdiği başarı olasılığı yine $\tfrac{1}{2}$'dir (bunu sıkı sıkıya kanıtlamak gerekir ama doğrudur). Yani strateji, tek bir mahkumun başarı olasılığını değiştirmez.

Ama strateji, mahkumların başarılarını bağımlı hale getirir. Rastgele stratejide her mahkumun başarısı bağımsızdır, dolayısıyla 100 mahkumun hepsinin başarısı $\tfrac{1}{2^{100}}$ olur. Döngü stratejisinde ise mahkumlar ya hep birlikte başarır ya hep birlikte başarısız olur — dolayısıyla "hepsinin başarısı" olasılığı, tek bir mahkumun olasılığına çok yaklaşır.

İstatistikçiler bu durumu bağımlılığın olumlu kullanılması olarak adlandırır. Bireysel başarı olasılığı sabit kalsa da, sonuçları aynı yöne çekerek grup başarısı dramatik biçimde artar.

Gerçek bir problem mi?

100 mahkum problemi 2003'te Danimarkalı bilgisayar bilimci Peter Bro Miltersen tarafından bir başka problem üzerine çalışırken keşfedildi. Onun makalesi başlangıçta bir "fıkra" olarak görüldü; sonra matematikçiler döngü stratejisinin doğruluğunu sıkıca kanıtladılar.

Bugün bu problem, kombinatorik karar kuramı ve bilgisayar biliminde (özellikle dağıtık algoritmaların alt sınırı analizinde) sevilen bir örnek olarak öğretiliyor. Pratik karşılığı şudur: bağımsız kararların aynı anda doğru olması zordur — ama doğru bir "ortak protokol" varsa, başarısızlıklar birlikte düşer.

Bir hayat dersi mi?

Aslında bu problem, matematik biliminin temel bir derslerinden birini açıkça gösterir:

Aynı bireysel olasılıklarla, çok farklı toplu sonuçlar elde edebilirsiniz.

Bir takımı yönetiyorsanız, bir şirketi koordine ediyorsanız, ya da bir krizi yönetiyorsanız — bireysel başarı olasılığı yeterli değildir. Asıl önemli olan, başarıların ne kadar bağımlı olduğudur. Bağımsız sistemlerde "ya hep" çok zordur; bağlı sistemlerde "ya hep" mümkün hâle gelir.

100 numaralı kutunun önünde durup, kendi adını arayan bir mahkum bunu bilemez tabii ki. Ama döngü stratejisi sayesinde, bilmediği bir matematik yasası onun lehinedir.