به نام خدا

در یک جزیره k انسان‌نما زندگی می‌کنند. این انسان‌نماها دو گونه‌اند: عده‌ای راست‌گو هستند و به هر پرسش جواب درست می‌دهند. عده‌ای دیگر دروغ‌گو هستند و به هر پرسش جواب نادرست می‌دهند.

اگر انسانی به این جزیره برود، می‌تواند با مطرح کردن پرسش‌هایی مانند پرسش‌های زیر که جواب آن‌ها بله یا خیر است، این دودسته را از هم تشخیص دهد.

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

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

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

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

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

n تبهکار به این جزیره فرار کرده‌اند. این افراد تبهکار، در پاسخ به هر پرسش هر طور که بخواهند جواب می‌دهند، یعنی گاهی جواب درست و گاهی جواب نادرست می‌دهند.

کارآگاهی وظیفه دارد به این جزیره رفته و با مطرح کردن پرسش‌هایی نظیر پرسش‌های فوق (فقط با جواب بله یا خیر) این تبهکاران را شناسایی و بازداشت کند.

فرض کنید که تبهکاران و انسان‌نماها از نظر شکل ظاهری تفاوتی ندارند ولی یکدیگر را خوب می‌شناسند و می‌دانند که هر کدام از چه گروهی (راست‌گو، دروغ‌گو یا تبهکار) هستند. همچنین می‌دانیم کارآگاه از قبل اطلاعی در مورد این‌که هر یک از ساکنین این جزیره از کدام گروه است، ندارد.

الف) ثابت کنید که اگر n=1 و k≥2، کارآگاه می‌تواند فرد تبهکار را شناسایی کند.

ب) ثابت کنید که در حالت کلی اگر k>n، کارآگاه می‌تواند افراد تبهکار را شناسایی کند.

ج) ثابت کنید که اگر k≤n، کارآگاه نمی‌تواند افراد تبهکار را شناسایی کند. یعنی افراد تبهکار می‌توانند طوری به پرسش‌های کارآگاه جواب دهند که کارآگاه هیچ‌گاه نتواند مطمئن شود که یک فرد، تبهکار است.