العثور على رقمك الخاص في صندوق

Question

100 سجين (أو بعض العدد الزوجي 2N :-)) موجودون في الغرفة أ.وهي مرقمة من 1 إلى 100.

واحدًا تلو الآخر (من السجين رقم 1 إلى السجين رقم 100، بالترتيب)، سيتم السماح لهم بالدخول إلى الغرفة B حيث ينتظرهم 100 صندوق (مرقمة من 1 إلى 100).يوجد داخل الصناديق (المغلقة) أرقام من 1 إلى 100 (يتم تبديل الأرقام الموجودة داخل الصناديق بشكل عشوائي!).

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

قبل دخول الغرفة ب، يمكن للسجناء الاتفاق على استراتيجية (خوارزمية).لا توجد وسيلة للتواصل بين الغرف (ولا يمكن ترك أي رسالة في الغرفة ب!).

هل هناك خوارزمية تزيد من احتمالية بقاء جميع السجناء على قيد الحياة؟ما الاحتمالية التي تحققها تلك الخوارزمية؟

ملحوظات:

• إن القيام بالأشياء بشكل عشوائي (ما تسميه "لا استراتيجية") يعطي بالفعل احتمالًا قدره 1/2 لكل سجين، ولكن احتمال بقاءهم جميعًا على قيد الحياة هو 1/2^100 (وهو منخفض جدًا).يمكن للمرء أن يفعل أفضل بكثير!

• لا يسمح للسجناء بإعادة ترتيب الصناديق!

• يُقتل جميع السجناء في المرة الأولى التي يفشل فيها السجين في العثور على رقمه. و لا يوجد اتصال ممكن.

• تَلمِيح:يمكن للمرء إنقاذ أكثر من 30 سجينًا في المتوسط, وهو أكثر بكثير من (50/100) * (50/99) * [...] * 1

Answer 1

تم شرح هذا اللغز في http://www.math.princeton.edu/~wwong/blog/blog200608191813.shtml وهذا الشخص يقوم بعمل أفضل بكثير في شرح المشكلة.

عبارة "مقتل جميع السجناء" خاطئة.إن عبارة "يمكنك توفير 30+ في المتوسط" خاطئة أيضًا شرط يقول أنه في 30% من الوقت يمكنك إنقاذ 100% من السجناء.

Answer 2

أجد أن الحل منخفض التقنية لهذا النوع من المشكلات هو دائمًا أفضل طريقة.

أولا نقوم ببعض الافتراضات حول الوضع

• السجناء ليسوا جميعهم مبرمجين أو علماء رياضيات
• إنهم لا يريدون أن يموتوا
• الحراس مسلحون بشكل جيد

لذا، مع وجود فرصة بنسبة 0.005% لرؤيتهم غدًا، هناك حل بسيط للغاية ومنخفض التقنية لهذه المشكلة. مكافحة الشغب

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

Answer 3

قم بتنفيذ خوارزمية الفرز وفرز المربعات حسب الأرقام الموجودة بداخلها.

يقوم السجين الأول بفرز 50 صندوقًا، ويقوم السجين الثاني بفرز الخمسين الأخرى ودمجها مع الأول.(لاحظ أن السجين الثاني يمكنه تخمين القيم الموجودة داخل الخمسين خانة الأولى)

بعد السجين الثاني ستكون كل الصناديق مرتبة !!!

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

Answer 4

لا أعرف ما إذا كان هذا مسموحًا به ولكن أفضل تقدير تقريبي يمكنني العثور عليه هو:

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

ابحث عن أول 50 عددًا أوليًا، لنفترض أننا نحتفظ بها في مصفوفة تسمى الأعداد الأولية.

• يدخل السجين الأول الغرفة B ويفتح الصندوق الأول ويجد الرقم m.
• انتظر الأعداد الأولية[1]^m (سيكون ذلك 3^m)
• افتح الصندوق 2 واقرأ الرقم --> n
• انتظر (الأعداد الأولية[2]^n - 1) * الأعداد الأولية[1]^m، سيكون ذلك (5^n - 1) * 3^m وسيكون إجمالي الوقت الذي كان ينتظره هو 3^n * 5^n

يكرر.بعد السجين الأول يكون الوقت الإجمالي له هو:3^م*5^ن*7^ع ...= س

قبل أن يدخل السجين الثاني إلى الغرفة، قم بتحليل X.أنت تعرف مسبقًا الأعداد الأولية التي تم استخدامها، لذا فإن التحليل أمر تافه.وبذلك تحصل على m وn وp وما إلى ذلك حتى يعرف السجين الثاني كل مجموعة مربع/رقم استخدمها السجين السابق.

احتمال أن يؤدي الأول إلى مقتل الجميع هو 1/2، والثاني سيكون له 50 / (100 - n) (وهو n عدد محاولات الأول) والثالث سيكون له 50 / (100 - n) - م) (إذا كان n + m = 100 فإن جميع المواضع معروفة) وهكذا.

من الواضح أن السجين التالي يجب أن يتخطى المربعات المعروفة بالفعل (باستثناء الخيار الأخير إذا كان المربع الذي يحتوي على رقمه معروفًا بالفعل)

لا أعرف ما هو الاحتمال الدقيق لأنه يعتمد على عدد الخيارات التي يتعين عليهم القيام بها ولكني أقول إنها عالية جدًا.

يحرر:إعادة القراءة، إذا لم يضطر السجين إلى التوقف عندما يحصل على رقمه، فإن احتمال المجموعة بأكملها يتحسن بشكل كبير، بالضبط 50%.

تحرير 2:@OysterD شاهد الأمر بهذه الطريقة.إذا كان السجين الأول يستطيع فتح 50 صندوقًا، فسيعرف الثاني ما إذا كان رقمه موجودًا في أي من تلك الصناديق.إذا كان الأمر كذلك، فيمكنه فتح 49 صندوقًا آخر (وبالتالي تعلم ترتيب المربع/الرقم للـ 100 صندوق) وفي النهاية يفتح الصندوق الخاص به.فإذا نجح السجين الأول ينجح الجميع.تذكر أن كل سجين يوفر طريقة للآخر ليعرف بالضبط مجموعة الصناديق/الأرقام لكل صندوق يفتحه.

Answer 5

ربما لم أقرأه بشكل صحيح، ولكن يبدو أن السؤال تم صياغته بشكل سيء أو يفتقد إلى المعلومات.

إذا وجد الرقم الذي تم تعيينه له في أحد هذه الصناديق الخمسين ، فإن السجين سيمشي إلى غرفة C ويتم إغلاق جميع الصناديق مرة أخرى قبل أن يسير الصناديق التالية إلى الغرفة B من الغرفة A.خلاف ذلك ، يتم قتل جميع السجناء (في الغرف A و B و C).

هل الجملة الأخيرة هناك تعني أن جميع السجناء يُقتلون في المرة الأولى التي يفشل فيها السجين في العثور على رقمهم؟إذا لم يكن الأمر كذلك، ماذا يحدث للسجناء الذين لم يجدوا رقمهم؟

إذا لم يكن هناك أي اتصال ممكن، وكلما دخل السجين إلى الغرفة "ب" وكان دائمًا في حالة مماثلة، فلن تكون هناك إمكانية لوضع استراتيجية.

يمكن للسجناء أن يقولوا قبل أن يغادروا الغرفة "أ" أي صندوق أرقام سيفتحونه.ولكن دون أن يعرف السجناء اللاحقون ما إذا كانوا ناجحين أم لا (بافتراض أن فشل أحدهم لا يعني فشل الجميع) عندما يدخل السجين التالي الغرفة "ب"، يظل لديهم نفس احتمالات اختيار رقمهم مثل السجين السابق (دائمًا 1:100). .

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

Answer 6

يمكن للسجناء أن يتفقوا على أن السجين 1 يفتح الصناديق 1-50.

إذا كانوا جميعًا على قيد الحياة، فإنهم يتفقون على أن يفتح السجين التالي الصناديق 2-51.(الرقم 2 تعسفي، ولكن من السهل تذكر هذه القاعدة) احتمالات بقائه على قيد الحياة نظرًا لنجاة P1 الآن 50/99.تريد التخلص من فتح الصندوق عندما تعلم أن الرجل السابق وجد صندوقه.

لا أعرف إذا كان هذا هو الأمثل، لكنه أفضل بكثير من العشوائي.

احتمال البقاء على قيد الحياة الذي يبدو

50/100 * 50/99 * 50/98 *. . .50/51 * 1

Answer 7

أعتقد أنه نظرًا لعدم إمكانية التواصل، فإن أفضل استراتيجية ستشمل

توزيع احتمالية كل سجين بالتساوي قدر الإمكان

هل أنا على الطريق الصحيح أم لا؟

المعلومات المتوفرة لكل سجين:

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

رأيي:

1. ارسم جدول أرقام مكون من عمودين، العمود الأول يحتوي على رقم الصندوق (من المربع رقم 1 إلى المربع رقم 100).يجب على كل سجين بعد ذلك اختيار 50 صندوقًا، وأي صندوق يختارونه، يجب عليه وضع علامة واحدة على الصف المقابل في العمود الثاني.
2. ومع ذلك، يُطلب من جميع السجناء عدم اختيار أي صندوق مرتين.ولا يجوز وضع علامة على أي مربع يزيد عن 50.قد يحصل بعض السجناء على خيارات أقل من غيرهم نظرًا لأن بعض الصناديق قد يتم ملؤها حتى 50 علامة أولاً.
3. عندما يتم نقل السجين إلى الغرفة ب، فإنه يفتح أي صناديق قام بوضع علامة عليها.

Answer 8

إذا قُتل جميع السجناء عندما فشل شخص ما في العثور على رقمهم، فعليك إما حفظ 100 أو 0.لا توجد وسيلة لإنقاذ 30 شخصا.

Answer 9

نفس المفهوم.

خذ آخر:

1. اكتب قائمة بأول 100 رقم ثنائي تحتوي على خمسين 1 و50 صفرًا.
2. رتبهم من الأدنى إلى الأعلى.
3. السجين رقم 1 يحصل على الرقم الأول، والسجين رقم 2 يحصل على الثاني، والسجين رقم 3 يحصل على الرقم الثالث، وهكذا...
4. يتذكر كل سجين رقمه الثنائي.
5. عندما يتم نقل أي سجين إلى الغرفة B، فإنه يقوم بعد ذلك بمطابقة الأرقام الثنائية للرقم الذي يتذكره مع كل صندوق، وتتم مطابقة أعلى بت مع المربع الموجود في أقصى اليسار، ويتم مطابقة أعلى بت التالي مع المربع الثاني الموجود في أقصى اليسار. ..تتم مطابقة أدنى بت مع المربع الموجود في أقصى اليمين.
6. يقوم بفتح أي مربعات مطابقة للرقم 1 ويترك الصناديق المغلقة المطابقة للرقم 0.

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

لم أفكر في الأرقام والأساس المنطقي الدقيق، ولكن هذا هو أحد الحلول السريعة التي يمكنني التفكير فيها في الوقت الحالي.

Answer 10

لا توجد أي حدود زمنية في السؤال، لذا أقترح أن يقرر السجناء أخذ ساعة واحدة لكل صندوق وفتحه بالترتيب المقدم.إذا سمح للسجين الثاني بالدخول إلى الغرفة بعد ساعتين، فإنه يعلم أن السجين الأول وجد رقمه الخاص في المربع 2.لذلك فهو يعلم أن تخطي المربع 2 في تسلسله ويفتح الصناديق 1 ، 3 ، 4 ... 51 احتمالات السجناء الأولى على الخسارة هي 50/100 إعطاء أن السجين الأول قد نجا ثم فرصة السجناء الثانية للفوز هي 50/99 لذا أجب يبدو أن ((50 ^51)*49!)/100!التي تسبق Google 2.89*10^-9 والتي لا شيء إلى حد كبير ، حتى لو كان السجناء يعرفون الصناديق التي وجدها المحظوظون سابقًا في عددهم ، فلن يكون هناك أمل