مقدمة: أعظم معجزة مناقضة للحدس في نظرية الاحتمالات

في عام 2003، طرح عالم الحاسوب الدنماركي بيتر برو ميلترسن (Peter Bro Miltersen) لغزاً شهيراً يُعرف باسم مسألة السجناء المئة (100 Prisoners Problem):

• يوجد $100$ سجين محكوم عليهم بالإعدام مرقمين من $1$ إلى $100$. في غرفة مغلقة يوجد $100$ صندوق تحتوي بداخلها على بطاقات مرقمة من $1$ إلى $100$ موزعة عشوائياً (تبديل $\sigma \in S_{100}$).
• القاعدة: يدخل كل سجين بمفرده بالتتابع ويحق له فتح $50$ صندوقاً كحد أقصى للعثور على رقمه. تُعاد الصناديق كما كانت بعد خروجه، ويُمنع منعاً باتاً أي تواصل بعد بدء اللعبة (لكن يُسمح بالاتفاق على خطة مسبقة).
• شرط النجاة: إذا نجح جميع السجناء المئة في إيجاد أرقامهم يُعفى عنهم جميعاً؛ أما إذا فشل سجين واحد فقط فيُعدم المئة جميعاً.

إذا فتح كل سجين $50$ صندوقاً عشوائياً (الاستراتيجية المستقلة)، فإن احتمال نجاح الفرد هو $1/2$، لكن احتمال نجاة الجميع معاً هو:

ومع ذلك، اكتشف سفين سكايوم (Sven Skyum) استراتيجية تتبع المؤشرات (Pointer-Following Strategy) التي ترفع احتمال نجاة الجميع إلى $31.18\%$ دون نقل بت واحد من المعلومات!

الفصل 1: تتبع المؤشرات وتفكيك الزمرة المتماثلة إلى دورات منفصلة

بالنسبة للسجين رقم $k \in \{1, \dots, 100\}$، تتلخص خطة سكايوم في:

1. الخطوة 1: افتح أولاً الصندوق رقم $k$.
2. الخطوة 2: إذا كانت البطاقة بداخله تحمل الرقم $x_1 = k$ فقد نجحت؛ وإذا كان $x_1 \neq k$، فافتح تالياً الصندوق رقم $x_1$.
3. الخطوة 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$ تقابل ثنائي، فإن الانطلاق من الصندوق $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$ هو:

1. اختيار $\ell$ عنصراً للدورة الطويلة: $\binom{2n}{\ell}$؛
2. ترتيبها في دورة دائرية واحدة: $(\ell - 1)!$؛
3. تبديل العناصر المتبقية وعددها $2n - \ell$: $(2n - \ell)!$.

بضرب المقادير تختصر المضاريب:

وبالقسمة على $|S_{2n}| = (2n)!$ نجد $\mathbb{P}(E_\ell) = \frac{1}{\ell}$. وباستخدام الأعداد التوافقية $H_N = \sum_{k=1}^N \frac{1}{k}$، يكون احتمال النجاة الدقيق:

وعند $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. الاقتران (Coupling): بما أن فشل شخص واحد يعادل في العقوبة فشل 51 شخصاً، تحشد استراتيجية الدورات جميع حالات الفشل داخل الـ $68.82\%$ من التباديل ذات الدورة $\ell > 50$، مما يترك $31.18\%$ من فضاء العينة خالياً تماماً من أي فشل!
2. التحصين ضد السجّان الخبيث: بالاتفاق مسبقاً على تقابل عشوائي سري $\tau \in S_{100}$، يضمن الترافق $\tau \sigma \tau^{-1}$ بقاء احتمال النجاة عند $31.18\%$.