هل من الممكن تحرير مئة سجين عبر أحجية؟
لغز -ال100- صندوق ، يشرح التبديلات العشوائة واستراتيجية الحلقات
1. طرح اللغز (تحدي 100 سجين)
يوجد 100 سجين، وكل منهم يملك رقمًا من 1 إلى 100 ، أخبرهم الحارس أن هنالك غرفة مليئة بالصناديق إذ أن هنالك 100 صندوق يطابق عددهم تماماً.
وكل صندوق مرقم من الخارج من 1 الى 100 ، يحتوي في داخل كل صندوق على ورقة فيها رقم عشوائي من 1 الى 100 .
يُسمح لكل سجين بدخول غرفة الصناديق وحده ، وفتح 50 صندوقًا فقط في محاولة عثور على رقمه الخاص.
إذا نجح جميع السجناء في العثور على أرقامهم، يُطلق سراحهم جميعًا؛ أما إذا فشل واحد فقط، فسيواجه الجميع عقوبة الإعدام.
2. استراتيجية البحث العشوائي
إذا فتح كل سجين 50 صندوقًا عشوائيًا، فإن احتمال أن يجد كل سجين رقمه هو (1/2) أي نص ، لكل سجين.
لذا الإحتمال الكلي لنجاح جميعهم يكون حوالي
(1/2)^100 = 0.0000000000000000000000000000008
وهو رقم صغير جدًا جداً ويكاد يكون مستحيلاً وبالعبارة الصريحة الإحتمال تقريباً يكون صفر
إذا ما العمل ما هي الاستراتيجية التي تمكنهم من النجاح ولو بنسبة أعلى من صفر ؟
3. استراتيجية “الحلقة” (Loop Strategy)
بدل البحث العشوائي، يتبع كل سجين طريقة ذكية مترابطة:
يبدأ بفتح الصندوق الذي يحمل رقمه.
إذا وجد ورقة برقم مختلف، يفتح الصندوق الذي يحمل رقم الورقة .
يكرر الخطوة حتى يجد رقمه أو يصل إلى حد 50 صندوقًا مفتوحًا.
طريقة العمل هذه تستند لفهم التركيب الرياضي للنظام على شكل حلقات (لووبز) في التوزيعات العشوائية.
إذ أن التوزيعات العشوائية اكتشف إحتوائها على حلقات منها قصيرة ومنها طويلة فمثلاً
إذا كان طول الحلقة التي ينتمي إليها السجين أقل من أو يساوي 50، فإنه حتمًا سيجد رقمه
فترتفع احتمالات النجاح إلى نحو 31٪ لاكن لماذا؟
إذا كانت أطول حلقة في التوزيع العشوائي ≤ 50
(وهو الحد المسموح)
سينجح جميع السجناء... و احتمالية ذلك حوالي 31٪.
إذا كانت هناك حلقة طولها أكبر من 50، فهذا يعني أن السجناء في تلك الحلقة لن يجدوا أرقامهم، وبالتالي سيفشل الجميع معًا
لاكن رغم هذا
الاحتمال يتقارب إلى قيمة ثابتة تقريبًا ~30.7 ٪ حتى عند زيادة عدد السجناء
— بسبب خصائص رياضية متعلقة باللوغاريتم الطبيعي.
أولًا: ما معنى “الحلقة” في هذا اللغز؟(توضيح )
كل صندوق يحتوي على رقم سجين.
عندما يبدأ سجين برقم معين بفتح الصندوق الذي يحمل رقمه، سيجد رقما آخر، فيفتح الصندوق الذي يحمل هذا الرقم... وهكذا.
هذه السلسلة تنتهي عندما يعود إلى رقمه الأصلي.
هذه السلسلة تُسمى “حلقة”
(Cycle).
مثال:
لو السجين رقم 12:
فتح الصندوق 12
وجد الرقم 47
ثم
فتح الصندوق 47
وجد الرقم 8
ثم
فتح الصندوق 8
وجد الرقم 12 (انتهت الحلقة)
إذًا: هذه حلقة من ثلاث عناصر
: [12 → 47 → 8 → 12]
و هنا نصل للجزء الرياضي :
عند ترتيب الأرقام من 1 إلى 100 بشكل عشوائي تمامًا داخل الصناديق، فإن هذا الترتيب يُمثل ما يُعرف في الرياضيات بـ:
تبديله عشوائية
(Random Permutation)
من الأرقام من 1 إلى 100.
المقصود هو ترتيب عشوائي بدون تكرار.
كل تبديله من هذه الأرقام يمكن تحليلها إلى عدة حلقات منفصلة.
بعض التبديلات تحتوي على حلقات قصيرة فقط
(مثلاً عشرة حلقات طول كل واحدة عشرة).
وبعضها فيها حلقة طويلة واحدة (مثلاً واحدة طولها ستون، والباقي أقصر).
وقد أثبت رياضيًا أنه عندما يكون عدد العناصر كبيرًا:
فإن الاحتمال ألا تحتوي التبديله على أي حلقة أطول من
( n/2 )
—(أي خمسون في حال المئة سجين)
هذه النتيجة تأتي من دراسة سلوك التوزيعات العشوائية .
عندما نزيد عدد السجناء مثلًا إلى 1000، فإن الحد الفاصل سيصبح 500.
لكن الاحتمال بأن تكون جميع الحلقات ≤ 500 يظل قريبًا من 30.7% أيضًا.
المراجع :
فيديو تفصيلي :
فيديو يشرح بسلاسة وسهولة أوضح :
—Ratio ≡ رَقِيم