هوپا، انجمن علم ایران

در یک جزیره تعدادي انسان نما زندگی می کنند. این انسان نما ها سه دسته اند: عده ای راستگو هستند و به هر پرسش جواب درست می دهند. عده ای دیگر دروغگو هستند و به هر پرسش جواب نادرست می دهند. عده اي ديگر نيز تبه كار هستند و به پرسشها به ميل خود گاهي درست و گاهي نادرست جواب مي دهند.
کارآگاهی وظیفه دارد به این جزیره رفته و با مطرح کردن پرسش هایی كه جوابشان بله يا خير است، این تبه کاران را شناسایی و بازداشت کند.
فرض کنید که انسان نما ها از نظر شکل ظاهری تفاوتی ندارند ولی یکدیگر را خوب می شناسند و می دانند که هر کدام از چه گروهی (راستگو، دروغگو یا تبهکار) هستند.
همچنين ميدانيم كه تعداد تبهكاران كمتر از نصف تعداد كل انسان نما ها است.
آيا كارآگاه ميتواند تبهكاران را شناسايي كند؟ اگر پاسختان مثبت است، روشي براي كارآگاه ارايه كنيد تا موفق به شناسايي و بازداشت آنها شود و اگر پاسختان منفي است، دليلتان را توضيح دهيد.

اولا اينكه اين كاراگاه هر نوع پرسشي رو ميتونه مطرح كنه يا نه؟
ثانيا افراد فقط پاسخ پرسشاي خودشونو ميدن يا تو كار ديگران ميتونن فضولي هم بكنن؟

1- همانطور كه در صورت مسئله آمده فقط پرسشهايي كه جوابشان بله يا خير باشد.
2- فقط پرسشهاي خودشان

به عنوان مثال، فرض کنید A راستگو و B دروغ گو است. در این صورت، پرسش ها و پاسخ ها می تواند به صورت زیر باشد:

پرسش از A : آیا B دروغگو است؟ جواب : بله

پرسش از A : آیا A و B دروغگو هستند؟ جواب: خیر

پرسش از B: آیا 2+2=4؟ جواب: خیر

پرسش از B: آیا تو دروغگو هستی؟ جواب: خیر

به نظر من كاراگاه اين شانس رو داره ولي دليل نداره كه بتونه حتما تبه كار ها رو پيدا كنه.
مثلا فرض كنيد تعداد كل افرادn است.ابتدا از همگي ان ها بپرسه كه آيا 2+2=4 است؟
مثلا k نفر مي گن بله و p نفر مي گن خير.پس:
k نفر راستگو يا راستگو و تبه كارن و p نفر دروغگو يا دروغگو و تبه كارن.چون در سوال گفته شده بود
كه تعداد تبه كارا از نصف كمتره پس در يكي از دو گروه بالا نيز تعداد تبه كارها از نصف اون تعداد هم كمتره.
حالا قدم بعدي اينه كه ببينه در كدوم گروه تبه كاران از نصف كمترن.براي انجام اين كار كاراكاه دو حالت پيشرو داره:
1-بره مثلا از تك تك افراد گروه pنفري بپرسه كه ايا شما راستگوييد؟اگه بيشتر از نصفشون بگن بله پس مشخص
ميشه كه در گروه kنفري تعداد تبه كاران كمتره پس بره تو گروه k نفري و اين گونه سوال بكنه:
فرض كنيد تعداد اعضاي k به صورت k1 k2 k3 ...kn باشد.بره پيشk1 و ازش سوال كنه ايا تو راستگويي؟
ايا k2راستگو است؟...ايا kn راستگو است؟و همين كار را براي تمامي اعضا انجام بده و نظر انها را در مورد
خود وديگران ثبت كنه و چون در اين گروه تعداد تبه كاران كمتر از نصفه پس در اين گروه راستگوها حداقل بيشتر از
نصف جواب بله ميارن و تبه كارا حداكثر كمتر از نصف جوابه بله ميارن زيرا فقط خودشون ميتونن به خودشون و هم نوعاشون
جواب بله بدن...پس تمام اونايي كه از نصف كمتر جواب بلي دارند(يعني نظر خود و ديگران براي خود اون شخص)
تبه كارن...يعني اگه مثلا k=6 باشه و مثلا 2 تبه كار(كمتر از نصف) و 4 راستگو(بيشتر از نصف) داشته باشيم
براي هر راستگو حداقل 4 جواب بلي و براي هر تبه كار حداكثر 2 جواب بلي موجود است....
بعد حالا از يكي از راستگوها استفاده كنه تا تبه كاراي گروه pنفري رو پيدا كنه(با سوال ايا فلان شخص تبه كار است)
همين حالت دقيقا مي تونه عكس بشه و تعداد تبه كارا تو گروهp نفري كمتر از نصف بشه و در اخر از دروغگو ها جهت
پيدا كردن تبه كارا تو گروه kنفري عمل كنه...
ولي حالا مساله جواب ديگه اي هم ميتونه داشته باشه:
مثلا اونجايي كه كارگاه براي تشخيص كه تو كدوم گروه تبه كارا از نصف بيشترن وقتي مثلا از گروه kنفري يه
سوال درست بپرسه(4=2+2) و تعداد بيشتر از نصف يا حتي نصفشون جواب بله بدن ديگه كاراگاه نميتونه بكنه...
البته راه هاي زيادي براي پرسش كردن مختلف است مثلا انقدر سوال درست كنه(مثلا از گروهk) تا تك تك افرادي كه
كه جواباي ضد و نقيض ميدن رو به عنوان تبه كار بگيره...ولي چون تبه كارا بر اساس ميل خودشون جواب ميدن
ممكنه دلشون بخواد تو گروهk نفري عين راستگو ها عمل كنن يا تو گروه pنفري عين دروغگوها عمل كنن
تا اصصلا كاراگاه نفهمه تو كدوم گروه تعداد تبه كارا از نصف بيشتره...
به خاطر همين به نظرم اي شانس رو داره ولي دليلي نداره كه حتما بتونه پيداشون كنه...
نميدونم...نظرم درسته؟

اول اينرا بگويم كه آنچه مد نظر سوال است، روشي است كه به طور قطعي(هميشه) بتواند تبه كاران را شناسايي كند.
به نظر من استدلال شما درست نيست.
شما براي اينكه اثبات كنيد پاسخ آن سوال مثبت است، كافي است يك روش ارايه كنيد و ثابت كنيد آن روش جواب قطعي مي دهد.
اما براي اينكه نشان دهيد پاسخ آن سوال منفي است، كافي نيست كه نشان دهيد طبق "يك" روش جواب قطعي به دست نمي آيد. چون اين گمان وجود خواهد داشت كه ايراد از روشتان باشد و روشهاي ديگري باشند كه جواب قطعي دهند.
بنابراين اگر ميخواهيد نشان دهيد كه پاسخ آن سوال منفي است، بايد ثابت كنيد "هيچ" روشي پاسخ قطعي نمي دهد. پس استدلالتان بايد كلي تر باشد.
متشكرم

یه سوال ایا تبه کاران برای فرار از دست کاراگاه سعی میکنن
یعنی ایا این فرار روی جوابشون تاثیر میذاره یا نه
ایا راست یا دروغشون 50-50 یا نه انسان های عاقلند .

ما اين را نميدانيم و تفاوتي هم در نتيجه ندارد، كارآگاه بهرحال بايد تمام حالتهاي ممكن براي پاسخگويي تبهكاران را در نظر بگيرد.
راست و دروغ آنها چه 50-50 باشد، چه 1-99 ، جواب آن مسئله يكسان خواهد بود.
روشي كه ارايه مي كنيد، بايد براي هر استراتژي هم كه تبهكاران براي پاسخگويي برگزينند، جواب قطعي دهد.

کاراگاه میتونه یک فرد خاص A رو در نظر بگیره و از دیگر اهالی جزیره(B) این سوال رو بپرسه:اگه من از A بپرسم آیا 2+2=6 چی جواب میده؟

حالا چندتا حالت بررسی میشه:

فرض کنید A راستگو باشد؛داریم:
B (آنکه قرار است سوال را جواب دهد)هم راستگو باشد:جواب=خیر
B دروغگو باشد:جواب=بله
B تبه کار باشه:بله یا خیر

حالا اگه A دروغگو باشه:
B راستگو باشه:جواب=بله
B دروغگو باشه:جواب=خیر
B تبه کار باشه:بله یا خیر

A تبه کار باشه:
B راستگو باشه:جواب=سکوت(چون نمیدونه A میخواد راست بگه یا دروغ)
B ردوغگو باشه:جواب=سکوت(مثل بالا)
B تبه کار باشه:جواب=باز هم سکوت(باز هم مثل بالا)

در مورد شخص A در دو مورد جواب می شنویم(راستگو یا دروغگو باشه) اما نمیتونیم بگیم که دقیقا راستگو هست یا دروغگو.
اما در یک مورد در مورد شخص مورد نظر اصلا جوابی نمی شنوید پس کاراگاه میفهمه اون شخص همون تبه کار هست!

اما سوال مهم اینه که تبه یعنی چی؟
منظورتون تبهکاره؟

ای بابا!من فکر کردم یه چیزی تو مایه های ماری جواناست که میکارنش!(مثل سبزی کاران)

راه حل جالبي ارايه داديد.
شايد بتوان بر طراح اين مسئله به خاطر مشخص نكردن مرز اطلاعات انسان نما ها ايراد گرفت، اما به نظر من فرض ضمني صورت سوال اينست كه انسان نما ها همه چيز دان هستند، يعني به تمام پرسشها پاسخ بله يا خير مي دهند. چون وارد شدن پارامتر ديگري مانند "نميدانم" در كنار بله و خير، مسئله را قدري متفاوت(و پيچيده) مي كند. همچنين با وجود اينكه در صورت مسئله فقط به آگاهي انسان نما ها از يكديگر اشاره شده است، در پرسش و پاسخ نمونه خود(كه آن را در پست سوم آوردم) جواب سوالي مانند "آيا 2+2=4؟" را در محدوده آگاهي آنها دانسته است.
شما چنين فرض كنيد كه انسان نماها پاسخ همه پرسشها را مي دانند.
در غير اينصورت اين معما چندان زيبا نخواهد بود و بايد سر اين بحث كرد كه انسان نماها عدد پي را تا چند رقم اعشار بلدند!
از دقت و نكته سنجي شما متشكرم.

MRM نوشته شده: اما سوال مهم اینه که تبه یعنی چی؟

از لغت نامه دهخدا (http://www.loghatnaameh.com)
تبه . [ ت َب َه ْ] (ص ) مخفف تباه باشد.
تبه کردن . [ ت َب َه ْک َدَ ] (مص مرکب ) تباه کردن . هلاک کردن . کشتن . نابود کردن

از همه می پرسیم آیا تو دروغ گویی ؟

د : دروغ گو
ر : راستگو
ت : تبه کار

د ها می گویند خیر
ر ها هم می گن خیر

اونایی که بله اند بعضی هاشون جدا می کنیم و تبه کارند

بعد از اون جدا شده ها از کسانی که خیر گفته سوال می کنیم آیا اینا ت هستند ؟

اگر جواب بله بود اون ر هست و از اون شخص در رابطه با تبه کار بودن کل جمعیت سوال می کنیم و جواب در میاد

یه مشکل پیش میاد که اگر همه ت ها بگن خیر اون موقع

از تمام افراد می پرسیم آیا تو راست گویی ؟

ر ها میگن بلی
د ها می گویند بلی
تبه کار ها ممکن است بگن همگی بله

بازم مشکل دار شد


یه راه دیگر اینست که دو نفر رو انتخاب کنیم از بقیه بپرسیم آیا این دو نفر از یه جنس اند ؟ (مثلاً هر دو راستگو اند ؟)
**********
پس از edit :
به علت انبوهی تعداد حالات ولش کردم ولی باید جواب بده ... البته فکر کنم باید این فرض شه که تبه کاران همگی به صورت شانسی یک پاسخ نمی دهند که اگر این فرض رو بکنیم راه اولم راحت تره ...

asmann نوشته شده: شما چنين فرض كنيد كه انسان نماها پاسخ همه پرسشها را مي دانند.

متوجه نشدم!
یعنی ما جواب 2+2=4 رو در حوزه اطلاعات انسان نما ها حساب نکنیم؟
و اینکه به نظر شما ایراد کار در گزینه نمیدانم (همون سکوت) هست؟

یه مقدار بیشتر توضیح بدید ممنون میشم.

مثلا فرض كنيد تعداد كل افرادn است.ابتدا از همگي ان ها بپرسه كه آيا 2+2=4 است؟
مثلا k نفر مي گن بله و p نفر مي گن خير.پس:
k نفر راستگو يا راستگو و تبه كارن و p نفر دروغگو يا دروغگو و تبه كارن.چون در سوال گفته شده بود
كه تعداد تبه كارا از نصف كمتره پس حداقل در يكي از دو گروه بالا نيز تعداد تبه كارها از نصف اون تعداد
هم كمتره.حالا قدم بعدي اينه كه ببينه در كدوم گروه تبه كاران از نصف كمترن تا بشه جداسازي انجام داد.
چون در اين صورت اگر مثلا گروه مورد نظر گروه k عضوي باشد انگاه با طرح سوال از تك
تك اعضاي اين گروه ميتوان راستگوها را مشخص كرد و مساله حل ميشود.يعني مثلا ازشخص
K1 پرسيد كه ايا راست گويي؟اياk2 رست گو است؟...ايا kn راست گوست؟
حال دوباره اين سوال ها را از تك تك اعضا بپرسيم بعد به هر بله 1 امتياز و به هر خير 0 امتياز
بدهد و بعد از اين به سادگي روشن است كه كمترين امتياز راستگويان از نصف بيشتر
و بيشترين امتياز تبه كاران از نصف كمتر است بنا براين امتياز هاي از نصف بيشتر
همان راست گويان هستند و مساله حل مي شود.اگر هم در گروه p عضوي تعدا اعضاي تبه كاران
كمتر از نصف باشد دقيقا به همين ترتيب است با اين تفاوت كه به جاي راست در پرسش ها و
بله در امتيازها دروغ وخير جايگزين ميشود.
اما راه تشخيص اينكه در كدام گروه تعداد تبه كاران كمتر از نصف است رو پيدا نكردم؟
به نظرتون راهي كه رفتم منطقيه؟اگه جوابتون مثبته لطفا كمك كنيد ببينيم تو كدوم گروه تبه كارها تعدادشون كمتر از نصفه...

بله تا اينجا خوب پيش رفتيد، اما به نظرم مي آيد كار در ادامه دشوار است.
راه حلهاي ساده تر و كوتاه تري وجود دارد.

MRM نوشته شده: متوجه نشدم!
یعنی ما جواب 2+2=4 رو در حوزه اطلاعات انسان نما ها حساب نکنیم؟
و اینکه به نظر شما ایراد کار در گزینه نمیدانم (همون سکوت) هست؟

یه مقدار بیشتر توضیح بدید ممنون میشم.

با وجود اينكه محدوده آگاهي انسان نماها بطور دقيق در صورت سوال تعيين نشده،
اما (با دلايلي كه گفتم) شما چنين فرض كنيد كه آنها پاسخ همه پرسشها را مي دانند.
پس ديگر سكوت، نمي دانم و ... دركار نيست. فقط بله يا خير.