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

تعريفًا بالموضوع، مشكلة المئة سجين هي مسألة رياضية في نظرية الاحتمالات والتوافيق، يتعين فيها على 100 سجين مرقّمين من 1 إلى 100 إيجاد أرقامهم داخل صناديق مغلقة، مع السماح لكل سجين بفتح 50 صندوقًا فقط، ومن دون التواصل مع الآخرين بعد دخول أول سجين. إذا نجح جميع السجناء في إيجاد أرقامهم، يُطلق سراحهم جميعًا. أما إذا أخفق أي واحد منهم، يُعدمون جميعًا. يبدو من الوهلة الأولى أن فرص النجاح معدومة، لكن توجد إستراتيجية ذكية تعطيهم فرصة واقعية للنجاة. وفيما يلي تفاصيل أوسع عن ذلك.
اقترح آنا غال وبيتر برو ميلتيرسن المسألة لأول مرة عام 2003.
نص المسألة
الحل
كذلك، «يعرض مدير سجن على 100 سجين من المحكوم عليهم بالإعدام فرصة أخيرة. هناك غرفة تحتوي على 100 صندوق مغلق، يُوضع داخل كل منها رقم لأحد السجناء بشكل عشوائي. يدخل السجناء واحدًا تلو الآخر، ويُسمح لكل منهم بفتح 50 صندوقًا بأي ترتيب. إذا وجد كل سجين رقمه داخل الصناديق، يُعفى الجميع من الإعدام. أما إذا فشل أحدهم، يُعدم الجميع. يُسمح للسجناء بالاتفاق على استراتيجية مسبقًا، لكن لا تواصل بينهم بعد دخول أول سجين.»
وفي هذا الصدد، إذا اختار كل سجين 50 صندوقًا بشكل عشوائي، فإن احتمال أن يجد السجين الواحد رقمه هو 50%. وبالتالي فإن احتمال نجاة الجميع هو (1/2)^100، أي ما يقارب 0.0000000000000000000000000000008.
بحسب الصياغة التي قدمها فيليب فلاجوليه وروبرت سيدجويك:
التاريخ
كذلك، ظهرت المسألة لأول مرة في بحث لـآنا غال وبيتر ميلتيرسن عام 2003. ثم تناولها لاحقًا إلوين بيرليكامب وجو بوهلر، وظهرت في كتب تعليمية مثل كتاب فلاجوليه وسيدجويك في التوافيق، وكتاب ريتشارد ستانلي في التوافيق الجبرية.
- انظر كذلك
- لغز مونتي هول
- نظرية الاحتمالات
- سجناء مونتي هول
- مراجع
- روابط خارجية
- فيديو قناة Veritasium عن المسألة
الاستراتيجية
ومن ناحية أخرى، بشكل مفاجئ، توجد إستراتيجية تضمن احتمال نجاة يزيد عن 30%. تعتمد على تتبع سلسلة متكررة من الصناديق بحسب محتوياتها، وليس اختيار الصناديق بشكل عشوائي:
كذلك، كل سجين بذلك يتتبع حلقة (دورة) معينة داخل التبديل العشوائي. تنجح الإستراتيجية فقط إذا لم تتجاوز أي دورة 50 عنصرًا.
- يبدأ السجين بفتح الصندوق الذي يحمل رقمه.
- إذا وجد رقمه، ينجو.
- إذا لم يجده، يفتح الصندوق الذي يحمل الرقم الموجود داخل الصندوق السابق.
- يكرر ذلك حتى يجد رقمه أو يفتح 50 صندوقًا.
مثال عملي
- إذا كان لدينا 8 سجناء وصناديق، ويُسمح لكل سجين بفتح 4 صناديق، وكان التوزيع:
- في هذا المثال، كل سجين يتتبع دورة، ويستطيع الوصول إلى رقمه ضمن 4 محاولات.
- تمثيل التبديل (الدورات)
إضافةً إلى ذلك، أما إذا وجدت دورة من طول أكبر من 50 (أو أكثر من نصف عدد السجناء)، فإن السجناء داخلها سيفشلون حتمًا.
ومن ناحية أخرى، تُشكل أرقام السجناء داخل الصناديق تبديلًا رياضيًا، يمكن تحليله إلى تبديلات دورية. في المثال السابق:
احتمال النجاح
احتمال ألا تتجاوز أي دورة الطول 50 يعادل:
أي نحو 31% من الحالات تنجح باستخدام هذه الإستراتيجية.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟