مائة سجين وخمسون صندوقًا

في هذا اللغز، يوجد 100 سجين يحمل كل منهم رقمًا من 1 إلى 100. قرر حارس السجن أن يعطي كل السجناء فرصة للهروب. وقام بإعداد تحد، إذا نجح فيه كل السجناء فإنهم يحصلون على حريتهم، لكنهم سيقتلون إن فشلوا!

التحدّي

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

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

يبدو أنه لا أمل!

للوهلة الأولى، يبدو أنه لا أمل في حل هذه المشكلة. في الواقع، يبدو أن فرصة السجناء في العثور على بطاقاتهم الخاصة دون أي خطأ شبه معدومة، خصوصًا وأنه ليس بإمكانهم التواصل فيما بينهم خلال عملية البحث.
يملك كل سجين فرصة 50:50 للعثور على بطاقته. هناك 100 صندوق، وله أن يفتح ما لا يزيد عن 50 منها للبحث عن بطاقته. اذا كان يفتح الصناديق عشوائيا فسوف يفتح نصفها، وقد تكون تذكرته في أحدها كما قد لا تكون في أي منها. لذلك فإن فرصة نجاحه هي ½.
بالنسبة لسجينين إثنين، إذا اختار كل منهما عشوائيًا، فإنه يملك كذلك فرصة ½ للنجاح، وبما أن لكل منهما فرصة ½، ففرصة كليهما في النجاح ½ × ½ = ¼.
(أي أن فرصة نجاحهما معاً هي مرة من أربع مرّات).
أما فرصة 3 سجناء فهي: ½ × ½ × ½ = ⅛.
مع 100 سجين، تكون الفرصة: ½ × ½ × … ½ × ½ (100 مرة).

فرصة نجاح كل السجناء ≈ 0،000000000000000000000000000008
هذه بالطبع فرصة ضئيلة جدا. يبدو أن السجناء في عداد الموتى!

نتيجة لاتصدّق!

إذا قام كل سجين بالتخمين عشوائيًا، ففرصة السجناء في النجاح ستكون ضعيفة جدًا، بل إن فرصتهم شبه معدومة!
هناك استراتيجية يمكن للسجناء إتباعها تعطيهم فرصة للهروب تزيد على 30%. وهذه نتيجة تكاد لاتصدّق. فرصة تفوق 30% لـ100 شخص هي جيدة جدًا، بل إنها أفضل من فرصة سجينين يقومان بالتخمين عشوائيًا (بيننا أعلاه أنها مساوية لـ¼ أي 25%). كيف يمكن لهذا أن يكون ممكنًا؟
من الواضح أن فرصة السجين الواحد لا يمكن أن تزيد عن 50% (لا توجد وسيلة لتبادل المعلومات)، ومع ذلك، هناك معلومة مخزنة في ترتيب البطاقات في الصناديق خاصة وأنه لا يمكن تعديل مواقع البطاقات بين زيارات السجناء، وبإمكاننا استخدام هذه المعلومة.

الحل

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

في نهاية المطاف يوجد إحتمالان: إمّا أن تجد بطاقتك، وإمّا أن تفتح الـ50 صندوقًا كلها. للوهلة الأولى، يبدو أن هذا لا يمكن أن يحدث أي فارق مقارنة باختيار الصناديق عشوائيا (وهذا صحيح، إن كنّا نتحدّث عن سجين واحد فقط)، ولكن لأن جميع السجناء الـ100 سوف يستخدمون نفس مجموعة الصناديق، فهذا يصنع فرقًا كبيرًا.
الجمال في هذا اللغز ليس معرفة الحل، ولكن معرفة لماذا هو حل ناجح!

لماذا ينجح هذا الحل؟

يحتوي كل صندوق بطاقة واحدة، وكل بطاقة تختلف عن الأخرى. وهذا يعني أن كل بطاقة هي إما في الصندوق الحامل لرقمها، أو أنها تشير إلى صندوق آخر. بما أن البطاقات مختلفة، فإن كل صندوق تشير إليه بطاقة واحدة لا غير.

إن فكرت في الأمر، فإن الصناديق تشكل بهذه الطريقة سلاسل دائرية. كل صندوق لا يمكن أن يكون إلا جزءا من سلسلة واحدة لأن هناك صندوقًا واحدًا يدل عليه في حين يدل هو على صندوق واحد (سيرى المبرمجون هنا علاقة لهذا بالقوائم المرتبطة).
إن لم يكن صندوق محتويًا على تذكرة تحمل رقمه، فإنه بالضرورة ينتمي إلى سلسلة. قد تكون بعض سلاسل قصيرة قدر صندوقين، بعضها أطول.
و بما أن السجين يبدأ بالصندوق الذي يحمل رقمه، فإن السلسلة ستحتوي بالضرورة على رقمه. وباتباع هذه السلسلة فإنه سيصل بالضرورة الى الصندوق الذي يحتوي رقمه. لكن السؤال هو: هل بإمكانه فعل ذلك قبل فتح كل الصناديق الخمسين؟

طول السلسلة

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

إحتمال وجود سلسلة طويلة

بعد أن أقنعت نفسك بأن النجاح يستلزم أن يكون الحد الأقصى لطول السلسلة أقل أو يساوي 50، وأنه لا يمكن أن توجد سوى سلسلة واحدة في أي مجموعة تحتوي سلسلة أكبر من خمسين، يمكننا حساب احتمالات النجاح كما يلي:
إحتمال النجاح = 1 – إحتمال وجود سلسلة أطول من 50.

القليل من الرياضيات

علينا العمل على إحتمال أن السلاسل الطويلة موجودة.

بالنسبة لسلسلة طولها L فإن عدد طرق ترتيب الصناديق هو:

في مجموعات الأرقام هذه توجد !(L-1) طريقة لترتيب البطاقات.
التذاكر المتبقية يمكن ترتيبها بـ!(L-100) طريقة (ولا تهمنا كيفية الترتيب، لأننا نعلم أنه لا يمكن لأي منها أن تكون في حلقة أكبر من 50).
وبجمعها، فإن عدد التبديلات التي تحتوي على سلسلة ذات طول يساوي l بالظبط (>50) يساوي:

توجد !100 طريقة لترتيب البطاقات، لذلك فإن إحتمال وجود سلسلة طولها L هو 1/L  فقط. وهذه نتيجة مذهلة لأنها مستقلّة عن عدد الصناديق.

بما أننا نعلم أنه لا يمكن أن تكون هناك سوى سلسلة واحدة طولها >50، فإن احتمال النجاح (Pr win) هو:

النتيجة

في 31,18% من الحالات، يكون أقصى طول سلسلة يتم تشكيلها أقل من 50 صندوقًا وهكذا فإن كل سجين سوف يكون قادرًا على العثور على بطاقته قبل أن يصل إلى حد الـ50 صندوقًا.
احتمال حصول جميع السجناء على تذاكرهم هو 31.18٪
وفيما يلي رسم بياني يوضح احتمالات (على المحور y) جميع السلاسل ذات الطول L (على المحور x). الأحمر يصور كل الإخفاقات (الانحناء هو ببساطة منحى 1\L). يظهر اللون الأخضر حالات النجاح (الحساب هنا أكثر تعقيدا، كما أن هناك عدة طرق لتحديد الطول الأقصى الأقل من 50). الاحتمال الكلي يصل إلى 31،18% بجمع قيمة القضبان باللون الأخضر.