مشكلة المئة سجين

مشكلة المئة سجين هي مسألة رياضية في نظرية الاحتمالات والتوافيق، يتعين فيها على 100 سجين مرقّمين من 1 إلى 100 إيجاد أرقامهم داخل صناديق مغلقة، مع السماح لكل سجين بفتح 50 صندوقًا فقط، ومن دون التواصل مع الآخرين بعد دخول أول سجين. إذا نجح جميع السجناء في إيجاد أرقامهم، يُطلق سراحهم جميعًا. أما إذا أخفق أي واحد منهم، يُعدمون جميعًا. يبدو من الوهلة الأولى أن فرص النجاح معدومة، لكن توجد استراتيجية ذكية تعطيهم فرصة واقعية للنجاة.

اقترح آنا غال وبيتر برو ميلتيرسن المسألة لأول مرة عام 2003.

 نص المسألة 
وفقًا للصياغة التي قدمها فيليب فلاجوليه وروبرت سيدجويك:

«يعرض مدير سجن على 100 سجين من المحكوم عليهم بالإعدام فرصة أخيرة. هناك غرفة تحتوي على 100 صندوق مغلق، يُوضع داخل كل منها رقم لأحد السجناء بشكل عشوائي. يدخل السجناء واحدًا تلو الآخر، ويُسمح لكل منهم بفتح 50 صندوقًا بأي ترتيب. إذا وجد كل سجين رقمه داخل الصناديق، يُعفى الجميع من الإعدام. أما إذا فشل أحدهم، يُعدم الجميع. يُسمح للسجناء بالاتفاق على استراتيجية مسبقًا، لكن لا تواصل بينهم بعد دخول أول سجين.»

إذا اختار كل سجين 50 صندوقًا بشكل عشوائي، فإن احتمال أن يجد السجين الواحد رقمه هو 50%. وبالتالي فإن احتمال نجاة الجميع هو (1/2)^100، أي ما يقارب 0.0000000000000000000000000000008.

 الحل 

 الاستراتيجية 
بشكل مفاجئ، توجد استراتيجية تضمن احتمال نجاة يزيد عن 30%. تعتمد على تتبع سلسلة متكررة من الصناديق وفقًا لمحتوياتها، وليس اختيار الصناديق بشكل عشوائي:

 يبدأ السجين بفتح الصندوق الذي يحمل رقمه.
 إذا وجد رقمه، ينجو.
 إذا لم يجده، يفتح الصندوق الذي يحمل الرقم الموجود داخل الصندوق السابق.
 يكرر ذلك حتى يجد رقمه أو يفتح 50 صندوقًا.

كل سجين بذلك يتتبع حلقة (دورة) معينة داخل التبديل العشوائي. تنجح الاستراتيجية فقط إذا لم تتجاوز أي دورة 50 عنصرًا.

 مثال عملي 
إذا كان لدينا 8 سجناء وصناديق، ويُسمح لكل سجين بفتح 4 صناديق، وكان التوزيع:

 رقم الصندوق 1  2  3  4  5  6  7  8 رقم السجين داخل الصندوق 7  4  6  8  1  3  5  2

في هذا المثال، كل سجين يتتبع دورة، ويستطيع الوصول إلى رقمه ضمن 4 محاولات.

 تمثيل التبديل (الدورات) 
تُشكل أرقام السجناء داخل الصناديق تبديلًا رياضيًا، يمكن تحليله إلى تبديلات دورية. في المثال السابق:

أما إذا وجدت دورة من طول أكبر من 50 (أو أكثر من نصف عدد السجناء)، فإن السجناء داخلها سيفشلون حتمًا.

 احتمال النجاح 
احتمال ألا تتجاوز أي دورة الطول 50 يعادل:

أي حوالي 31% من الحالات تنجح باستخدام هذه الاستراتيجية.

 التاريخ 
ظهرت المسألة لأول مرة في بحث لـآنا غال وبيتر ميلتيرسن عام 2003. ثم تناولها لاحقًا إلوين بيرليكامب وجو بوهلر، وظهرت في كتب تعليمية مثل كتاب فلاجوليه وسيدجويك في التوافيق، وكتاب ريتشارد ستانلي في التوافيق الجبرية.

 انظر أيضًا 
 لغز مونتي هول
 نظرية الاحتمالات
 سجناء مونتي هول

 مراجع 

 روابط خارجية 
 فيديو قناة Veritasium عن المسألة
 Wolfram MathWorld - 100 Prisoners Problem

تصنيف:تبديلات (توافيقيات)
تصنيف:رياضيات مسلية
تصنيف:مفارقات نظرية الاحتمالات