in

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

في هذا اللغز، يوجد 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% بجمع قيمة القضبان باللون الأخضر.

  • ترجمة: شهاب برقاوي.
  • تدقيق لغوي: رضى جيلاني.

ماتقييمك للموضوع؟

15 تعليق

ضع تعليقك
  1. بالطبع انه حل عبقري فسنتوصل في النهاية لنتيجة افضل بعدد صناديق اقل ربما , انا أشجع بنشر المزيد من الألغاز هذه التي تربط العقل بالرياضيات

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

    فل نفرض انه كل صندوق يحمل رقم بطاقة الصندوق الذي قبله مثال
    الصندوق 1 يحمل بطاقة رقم 2 و الصندوق 2 يحمل بطاقة الصندوق 3 الى اخره حتى نصل الى الصندوق 100 الذي يحمل بطاقة رقم 1
    في هذه الحالة كل السلاسل سوف تكون طولها 100 أي اكبر من 50
    لا أدري ان كنتم قد كتبتم الجملة بشكل خاطئ أو المعلومة اصلا خاطئة
    لا يمكن ان يكون هناك سوى سلسلة واحدة أطول من خمسين في اي تشكيلة …. كيف يمكن ذلك لان هذا شيئ لا اساس له من الصحة

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

    • بهذا الافتراض ستكون سلسلة واحدة تتكون من 100 والفرق فقط سيكون من أين ستبدأ في هذه السلسلة ولكنها في النهاية واحدة فقط

    • حينها سيعلم السجين ان البطاقات تم ترتيبها بشكل : مكان البطاقة في الصندوق رقم ( رقم البطاقة -1 )
      و منه رقم بطاقته في الصندوق الذي يحمل رقم أقل من بطاقته بـ 1
      اذا كانت بطاقته 5 سيبدأ بالعد من 5 الى 25 الى ان يدرك انها مرتبة بشكل صحيح فيذهب الى الصندوق ( 4 ) خهخ و يكون الحل حينها أسهل و مضمون 100% بدل 30%

  3. الحل خاطئ اذ من الممكن ان يكون الشخص يبحث عن رقمه في سلسلة مختلفة عن السلسة التي تحوي رقمه .

    • لا يمكن حدوث ذلك
      لاحظ أنه بدأ بفتح الصندوق الذي مكتوب عليه رقم السجين وحتى يعود لهذا الصندوق مرة أخرى يجب أن يعثر على البطاقة التي تحتوي على هذا الرقم
      ولذلك يجب أن تحتوي السلسلة المغلقة على رقمه 🙂
      الفكرة حقا عبقرية

  4. الفكرة والتحليل المتسلسل والمنطقي رائع
    اذا وجد احدهم بطاقته التي تحمل رقمه فيقل عدد الصناديق صندوقا وتزيد احتنال نجاح عثور السجين التالي على طاقته اكثر لحين ان يصل الاحتمال 100% لاخر سجين ومن الممكن ان يبدأ السجين بطرح رقمه من المئة والبدئ حس التسلسل اعلاه فتزيد احتماله لايجاد بطاقته بمايزيد عن 40%

  5. أسهل شئ … هو يتفق السجناء على أول 50 صندوق ليفتحهم كل السجناء و بالتالي تكون الفرصة 50/50 بالنسبة للمئة سجين و لتحسين الفرص إذا نجح من 50 أكثر من 25 فسيقمون ال 50 المتبقيين من فتح النصف الأخر من الصَّناديق و بالتالي تكون عدد النجحين أكثر من خمسين 😉

  6. اليش من الافضل و الابسط و الاسهل و الاقل تعقيدا و الاكبر بنسبة النجاح ان يتفق الجميع على فتح ٥٠ صندوق معين، عندها نسبة النجاح ٥٠٪‏

  7. طيب الشخص الي لقي بطاقتو واخذها ممكن الشخص الي ورا ما يشوف هاي البطاقة ويكون الصندوق فارغ

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني.

هل هناك علاقة بين الشطرنج والرياضيات؟

أخطار الحمية النباتية طويلة الأمد