مشكلة تتعلق بالسجناء والقبعات التي يجب تحديد لونها
استجمام / / December 31, 2020
يرى نظام الإغلاق جميع الأحرف الكبيرة ، ولكن يمكنه فقط نطق "أسود" أو "أبيض" ، مع إبلاغ الجميع في نفس الوقت بالمعلومات المخفية. لا يعرف السجناء العدد الإجمالي للقبعات السوداء والبيضاء ، وهناك أكثر من خيارين محتملين. لكنها تقتصر على نسختين فقط عندما يتعلق الأمر بمفهوم التكافؤ: يمكن أن يكون الرقم زوجيًا أو فرديًا.
مفتاح حل المشكلة هو: يتفق السجناء على أن المستجيب الأول سيقول ، على سبيل المثال ، "أسود" ، إذا رأى عددًا فرديًا من الأحرف الاستهلالية السوداء في المقدمة ، و "الأبيض" إذا رأى عددًا زوجيًا من الأسود قبعات.
دعونا نلقي نظرة على المثال من الصورة أعلاه. يرى أطول سجين رقم 1 ثلاث قبعات سوداء أمامه. يتكلم "الأسود" بصوت عال. هذا يعطي كل شخص آخر المعلومات التي تفيد بوجود عدد فردي من الأحرف الاستهلالية السوداء في المستقبل. أخطأ السجين الأول في لون قبعته ، لكن هذه ليست مشكلة كبيرة: بمجرد السماح له بالإجابة بشكل غير صحيح.
ترى السجين رقم 2 أمامها عددًا فرديًا من القبعات السوداء. تدرك أنها بيضاء وتجيب بشكل صحيح. يرى السجين رقم 3 عددًا زوجيًا من القبعات السوداء ويخمن أنه يرتدي قبعة سوداء رآها السجين الأولين.
تسمع الأسيرة رقم 4 الإجابة وتدرك أنها يجب أن تبحث عن عدد زوجي من القبعات السوداء ، لأنه كان هناك قبعة سوداء خلف ظهرها ، لكنها لا ترى سوى واحدة أمامها وتخلص إلى أن قبعتها سوداء. يبحث السجناء رقم 5-9 عن عدد فردي من القبعات السوداء ، والتي يرونها للتو ، بينما يدركون أنهم يرتدون قبعات بيضاء. يأتي الدور إلى السجين العاشر. إذا رأى السجين رقم 9 عددًا فرديًا من القبعات السوداء ، فهذا يعني شيئًا واحدًا فقط - السجين رقم 10 لديه غطاء أسود.
هذه هي الطريقة التي ستعمل بها هذه الخوارزمية لأي مجموعة من hubcaps. بالنسبة للمشارك الأول ، فإن احتمال الإجابة غير الصحيحة هو 50٪ ، لكن المعلومات المتعلقة بالتكافؤ الزوجي الفردي ، التي سيقدمها ، ستسمح لبقية الأسرى بتخمين لون الغطاء.
سيبدأ كل مجيب في تقدير عدد الأحرف الاستهلالية الفردية والزوجية. إذا كان الرقم المحسوب في العقل لا يتطابق مع ما يراه ، فإن قبعته هي نفس اللون. في كل مرة في هذه الحالة ، يأخذ المستجيب التالي في الاعتبار أن العدد الزوجي من الأحرف الاستهلالية المتبقية قد تغير الآن.
هذا اللغز هو ترجمة لفيديو TED-Ed.