مقدمة: أعظم معجزة مناقضة للحدس في نظرية الاحتمالات
في عام 2003، طرح عالم الحاسوب الدنماركي بيتر برو ميلترسن (Peter Bro Miltersen) لغزاً شهيراً يُعرف باسم مسألة السجناء المئة (100 Prisoners Problem):
- يوجد \(100\) سجين محكوم عليهم بالإعدام مرقمين من \(1\) إلى \(100\). في غرفة مغلقة يوجد \(100\) صندوق تحتوي بداخلها على بطاقات مرقمة من \(1\) إلى \(100\) موزعة عشوائياً (تبديل \(\sigma \in S_{100}\)).
- القاعدة: يدخل كل سجين بمفرده بالتتابع ويحق له فتح \(50\) صندوقاً كحد أقصى للعثور على رقمه. تُعاد الصناديق كما كانت بعد خروجه، ويُمنع منعاً باتاً أي تواصل بعد بدء اللعبة (لكن يُسمح بالاتفاق على خطة مسبقة).
- شرط النجاة: إذا نجح جميع السجناء المئة في إيجاد أرقامهم يُعفى عنهم جميعاً؛ أما إذا فشل سجين واحد فقط فيُعدم المئة جميعاً.
إذا فتح كل سجين \(50\) صندوقاً عشوائياً (الاستراتيجية المستقلة)، فإن احتمال نجاح الفرد هو \(1/2\)، لكن احتمال نجاة الجميع معاً هو:
\[\mathbb{P}(\text{نجاة الجميع})_{\text{مستقل}} = \left(\frac{1}{2}\right)^{100} \approx 7.89 \times 10^{-31}\]ومع ذلك، اكتشف سفين سكايوم (Sven Skyum) استراتيجية تتبع المؤشرات (Pointer-Following Strategy) التي ترفع احتمال نجاة الجميع إلى \(31.18\%\) دون نقل بت واحد من المعلومات!
الفصل 1: تتبع المؤشرات وتفكيك الزمرة المتماثلة إلى دورات منفصلة
بالنسبة للسجين رقم \(k \in \{1, \dots, 100\}\)، تتلخص خطة سكايوم في:
- الخطوة 1: افتح أولاً الصندوق رقم \(k\).
- الخطوة 2: إذا كانت البطاقة بداخله تحمل الرقم \(x_1 = k\) فقد نجحت؛ وإذا كان \(x_1 \neq k\)، فافتح تالياً الصندوق رقم \(x_1\).
- الخطوة 3: اقرأ الرقم الجديد \(x_2\) وافتح الصندوق رقم \(x_2\)، متتبعاً السلسلة \(k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots\) حتى تجد \(k\) أو تستنفد \(50\) محاولة.
flowchart TD
Start["يدخل السجين k الغرفة (بحد أقصى 50 محاولة)"]
Step1["الخطوة 1: فتح الصندوق k وقراءة البطاقة x = σ(k)"]
Check{"هل البطاقة x == k ؟"}
Win["تم العثور على الرقم k بنجاح!"]
Limit{"هل الصناديق المفتوحة < 50 ؟"}
Next["تتبع المؤشر: فتح الصندوق x (x ← σ(x))"]
Lose["لم يُعثر عليه في 50 خطوة: إعدام الجميع"]
Start --> Step1 --> Check
Check -- "نعم" --> Win
Check -- "لا" --> Limit
Limit -- "نعم" --> Next --> Check
Limit -- "لا (طول الدورة ℓ > 50)" --> Lose
لماذا تنجح هذه الطريقة؟ إن التقابل صندوق \(\mapsto\) بطاقة هو تقابل ثنائي \(\sigma\) في الزمرة المتماثلة \(S_{2n}\) (\(2n=100\)). وكل تبديل منتهٍ يتفكك بطريقة وحيدة إلى جداء دورات منفصلة (Disjoint Cycles):
\[\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100\]وبما أن \(\sigma\) تقابل ثنائي، فإن الانطلاق من الصندوق \(k\) يقود السجين حتماً حول الدورة المغلقة الوحيدة التي تحوي \(k\) ليصل في نهايتها إلى \(\sigma^{-1}(k)\) (الصندوق الذي يحوي البطاقة \(k\)). وعليه:
- ينجح السجين \(k\) خلال \(\le 50\) خطوة إذا وفقط إذا كان طول دورته \(\ell \le 50\).
- ينجو السجناء المئة جميعاً إذا وفقط إذا خلا التبديل \(\sigma \in S_{100}\) من أي دورة يزيد طولها على \(50\) (\(\ell > 50\))!
الفصل 2: عدّ الدورات الطويلة والأعداد التوافقية (\(1 - \ln 2\))
لعدد \(2n\) من السجناء (\(n = 50\))، لا يمكن للتبديل \(\sigma \in S_{2n}\) أن يحوي أكثر من دورة واحدة بطول \(\ell > n\)، لأن دورتين منفصلتين بطول \(> n\) تتطلبان \(2n+2 > 2n\) عنصراً على الأقل. إذن الأحداث \(E_\ell := \{\sigma \text{ يحوي دورة بطول } \ell\}\) للقيم \(\ell = n+1, \dots, 2n\) متنافية مثنى مثنى! وعدد التباديل في \(E_\ell\) هو:
- اختيار \(\ell\) عنصراً للدورة الطويلة: \(\binom{2n}{\ell}\)؛
- ترتيبها في دورة دائرية واحدة: \((\ell - 1)!\)؛
- تبديل العناصر المتبقية وعددها \(2n - \ell\): \((2n - \ell)!\).
بضرب المقادير تختصر المضاريب:
\[|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}\]وبالقسمة على \(|S_{2n}| = (2n)!\) نجد \(\mathbb{P}(E_\ell) = \frac{1}{\ell}\). وباستخدام الأعداد التوافقية \(H_N = \sum_{k=1}^N \frac{1}{k}\)، يكون احتمال النجاة الدقيق:
\[\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\%}\]وعند \(2n = 100\) نحصل على \(P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31.1828\%}\)!
الفصل 3: اقتران المخاطر (Coupling) بدون نقل معلومات
flowchart TD
Pool["إجمالي المخاطر ثابت: توقع الفشل E[فشل] = 50"]
Indep["الاستراتيجية المستقلة: الفشل مبعثر في جميع الأكوان تقريباً"]
Cycle["تتبع الدورات: ربط المصائر ببنية دورات σ"]
ResI["فشل واحد على الأقل في 99.99...92% من الأكوان ← النجاة ≈ 7.89×10⁻³¹"]
ResC["تركيز الفشل في 68.82% (ℓ>50) ← نجاة 100% في 31.18% من الأكوان!"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| الخاصية | 1. الاستراتيجية المستقلة | 2. استراتيجية الدورات |
|---|---|---|
| نجاح الفرد \(\mathbb{P}(A_k)\) | \(50.00\%\) | \(50.00\%\) (مطابق) |
| توقع الناجين \(\mathbb{E}[X]\) | \(50\) سجيناً | \(50\) سجيناً (مطابق) |
| الارتباط الإحصائي | معدوم (استقلال) | مقترن بقوة عبر \(\sigma\) |
| نجاة الـ \(100\) معاً | \((1/2)^{100} \approx 7.89 \times 10^{-31}\) | \(1 - (H_{100} - H_{50}) \approx 31.18\%\) |
| النهاية \(n \to \infty\) | \(0\) | \(1 - \ln 2 \approx 30.685\%\) |
- الاقتران (Coupling): بما أن فشل شخص واحد يعادل في العقوبة فشل 51 شخصاً، تحشد استراتيجية الدورات جميع حالات الفشل داخل الـ \(68.82\%\) من التباديل ذات الدورة \(\ell > 50\)، مما يترك \(31.18\%\) من فضاء العينة خالياً تماماً من أي فشل!
- التحصين ضد السجّان الخبيث: بالاتفاق مسبقاً على تقابل عشوائي سري \(\tau \in S_{100}\)، يضمن الترافق \(\tau \sigma \tau^{-1}\) بقاء احتمال النجاة عند \(31.18\%\).