بله، کارآگاه میتواند بزهکاران را شناسایی کند.
کارآگاه نخست یک سوال با پاسخ معلوم از همه میپرسد، مثلاً: «آیا همه افراد راستگو هستند؟» و همه را در دو مجموعه دستهبندی میکند.
کسانی که پاسخ منفی دهند، یا راستگو هستند و همیشه راست میگویند، یا بزهکار هستند و اتفاقی راست گفتهاند (مجموعه A)
کسانی که پاسخ مثبت دهند، یا دروغگو هستند و همیشه دروغ میگویند، یا بزهکار هستند و اتفاقی دروغ گفتهاند (مجموعه B)
سپس از همه این سوال را میپرسد: «آیا فرد a1 از مجموعه A راستگو است؟»
اگر مجموع افراد مجموعه B که پاسخ منفی دادهاند و افراد مجموعه A که پاسخ مثبت دادهاند، از نصف کل کمتر نباشد، اگر a1 بزهکار باشد، در اینصورت افراد فوق بزهکارند (اگر عضو B باشند راست گفتهاند و نمیتوانند دروغگو باشند و اگر عضو A باشند دروغ گفتهاند و نمیتوانند راستگو باشند)، و در نتیجه افراد بزهکار بیشتر یا مساوی نصف هستند که خلاف فرض است؛ لذا a1 نمیتواند بزهکار باشد و راستگو است.
اگر برعکس، مجموع افراد مجموعه B که پاسخ مثبت دادهاند و افراد مجموعه A که پاسخ منفی دادهاند، از نصف کل بیشتر باشد، اگر a1 راستگو باشد، در اینصورت افراد فوق بزهکارند (اگر عضو B باشند راست گفتهاند و نمیتوانند دروغگو باشند و اگر عضو A باشند دروغ گفتهاند و نمیتوانند راستگو باشند)، و در نتیجه افراد بزهکار بیشتر از نصف هستند که خلاف فرض است؛ لذا a1 نمیتواند راستگو باشد و بزهکار است.
اگر a1 راستگو بود، کارآگاه کلیه بزهکاران را توسط وی شناسایی میکند، اما اگر بزهکار بود، کارآگاه سوال فوق را در مورد a2 (و a3 و ...) از همه میپرسد و مرحله فوق را تکرار میکند تا عضو راستگویی از مجموعه A بیابد و بزهکاران را توسط وی شناسایی کند.
تبه كاران را پيدا كنيد!
- rohamavation
نام: roham hesami radرهام حسامی راد
محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2
عضویت : سهشنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴
پست: 3265-
سپاس: 5494
- جنسیت:
تماس:
Re: تبه كاران را پيدا كنيد!
جواب شما ساده هست شما در این جزیره قدم می زنید و با یک بومی ملاقات می کنید ، که می تواند دروغگو باشد یا یک راستگو ، و می خواهید بدانید که او چه نوع آدمی است. بنابراین شما از او می پرسید
- آیا شما یک راستگو هستید؟
وقتی او در حال پاسخ دادن است ، آتشفشان سر و صدای زیادی ایجاد می کند و شما نمی توانید جواب آن را بشنوید. بنابراین دوباره از او سال می کنید
- ببخشید من نمی توانستم حرف شما را بشنوم ، گفتید راستگو بودید؟ - و او جواب می دهد
- نه ، من این حرف را نزدم ، گفتم من دروغگو هستم.
آیا بومی دروغگو است یا راستگو
(نکته: به این فکر کنید که بومی ها در ابتدا می توانند به یک راست پاسخ دهند و سپس دروغگو بگویند)
حال فرض کنید با سه نفر ملاقات کرده اید ، A ، B و C اولین جزیره را تشکیل می دهند (بنابراین آنها یا دروغگو هستند یا راستگو هستند). شما از A می پرسید:
- در بین شما چند نفر حقیقت گوی هستند؟
دوباره ، وقتی آتشفشان جواب می دهد صدای بلندی ایجاد می کند و شما نمی توانید جواب را بشنوید. بنابراین شما از B می پرسید:
- الف چی گفت؟ - و B پاسخ می دهد
- A گفت که یکی از ما حقیقت گوی است و دو نفر دروغگو - و سپس C اضافه می کند
- حرف B را باور نکن ، او دروغ می گوید.
چه طبقه ای از افراد B و C هستند؟
دوباره فرض کنید که با سه نفر A ، B و C از جزیره ملاقات کرده اید. شما از A می پرسید:
- دروغگو هستی؟
دوباره ، وقتی آتشفشان جواب می دهد صدای بلندی ایجاد می کند و شما نمی توانید جواب را بشنوید. بنابراین شما از B می پرسید:
- الف چی گفت؟ - و B پاسخ می دهد
- A گفت که او دروغگو است - و سپس C اضافه می کند
- حرف B را باور نکن ، او دروغ می گوید.
چه طبقه ای از افراد B و C هستند؟
این بار با دو نفر الف و ب ملاقات می کنید
- یا من دروغگو هستم ، یا ب حقیقت گو است.
چه طبقه ای از افراد B است.
یک بار در جزیره با دو نفر آشنا شدم و از یکی از آنها پرسیدم:
- آیا یکی از شما راستگو است؟
با پاسخ او توانستم راه حل سوال خود را بدانم. چه طبقه ای از مردم بودند؟
سه نفر ، A ، B و C به جرم قضاوت می شوند. هر یک از این افراد می توانستند از جزیره بیایند یا نمی توانند. به یاد بیاورید که همه کسانی که از این جزیره می آیند یا دروغگو هستند یا راستگو هستند. افرادی که از این جزیره نمی آیند ، عادی خوانده می شوند و ممکن است حقیقت را بگویند یا نگویند.راستگو است. مظنونان گفتند:
ج: "من بی گناه هستم."
ب: "این درست است."
C: "B از جزیره می آید."
این سوال المپیاد کامپیوتر سالهای خیلی قبل بوده
در یک جزیره k انساننما زندگی میکنند. این انساننماها دو گونهاند: عدهای راستگو هستند و به هر پرسش جواب درست میدهند. عدهای دیگر دروغگو هستند و به هر پرسش جواب نادرست میدهند.
اگر انسانی به این جزیره برود، میتواند با مطرح کردن پرسشهایی مانند پرسشهای زیر که جواب آنها بله یا خیر است، این دودسته را از هم تشخیص دهد.
به عنوان مثال، فرض کنید A راستگو و B دروغگو است. در این صورت، پرسشها و پاسخها میتواند به صورت زیر باشد:
پرسش از A: آیا B دروغگو است؟ جواب: بله
پرسش از A: آیا A و B دروغگو هستند؟ جواب: خیر
پرسش از B: آیا ۲+۲=۴ ؟ جواب: خیر
پرسش از B: آیا تو دروغگو هستی؟ جواب: خیر
n تبهکار به این جزیره فرار کردهاند. این افراد تبهکار، در پاسخ به هر پرسش هر طور که بخواهند جواب میدهند، یعنی گاهی جواب درست و گاهی جواب نادرست میدهند.
کارآگاهی وظیفه دارد به این جزیره رفته و با مطرح کردن پرسشهایی نظیر پرسشهای فوق (فقط با جواب بله یا خیر) این تبهکاران را شناسایی و بازداشت کند.
فرض کنید که تبهکاران و انساننماها از نظر شکل ظاهری تفاوتی ندارند ولی یکدیگر را خوب میشناسند و میدانند که هر کدام از چه گروهی (راستگو، دروغگو یا تبهکار) هستند. همچنین میدانیم کارآگاه از قبل اطلاعی در مورد اینکه هر یک از ساکنین این جزیره از کدام گروه است، ندارد.
الف) ثابت کنید که اگر n=1 و k≥2، کارآگاه میتواند فرد تبهکار را شناسایی کند.
ب) ثابت کنید که در حالت کلی اگر k>n، کارآگاه میتواند افراد تبهکار را شناسایی کند.
ج) ثابت کنید که اگر k≤n، کارآگاه نمیتواند افراد تبهکار را شناسایی کند. یعنی افراد تبهکار میتوانند طوری به پرسشهای کارآگاه جواب دهند که کارآگاه هیچگاه نتواند مطمئن شود که یک فرد، تبهکار است.
- آیا شما یک راستگو هستید؟
وقتی او در حال پاسخ دادن است ، آتشفشان سر و صدای زیادی ایجاد می کند و شما نمی توانید جواب آن را بشنوید. بنابراین دوباره از او سال می کنید
- ببخشید من نمی توانستم حرف شما را بشنوم ، گفتید راستگو بودید؟ - و او جواب می دهد
- نه ، من این حرف را نزدم ، گفتم من دروغگو هستم.
آیا بومی دروغگو است یا راستگو
(نکته: به این فکر کنید که بومی ها در ابتدا می توانند به یک راست پاسخ دهند و سپس دروغگو بگویند)
حال فرض کنید با سه نفر ملاقات کرده اید ، A ، B و C اولین جزیره را تشکیل می دهند (بنابراین آنها یا دروغگو هستند یا راستگو هستند). شما از A می پرسید:
- در بین شما چند نفر حقیقت گوی هستند؟
دوباره ، وقتی آتشفشان جواب می دهد صدای بلندی ایجاد می کند و شما نمی توانید جواب را بشنوید. بنابراین شما از B می پرسید:
- الف چی گفت؟ - و B پاسخ می دهد
- A گفت که یکی از ما حقیقت گوی است و دو نفر دروغگو - و سپس C اضافه می کند
- حرف B را باور نکن ، او دروغ می گوید.
چه طبقه ای از افراد B و C هستند؟
دوباره فرض کنید که با سه نفر A ، B و C از جزیره ملاقات کرده اید. شما از A می پرسید:
- دروغگو هستی؟
دوباره ، وقتی آتشفشان جواب می دهد صدای بلندی ایجاد می کند و شما نمی توانید جواب را بشنوید. بنابراین شما از B می پرسید:
- الف چی گفت؟ - و B پاسخ می دهد
- A گفت که او دروغگو است - و سپس C اضافه می کند
- حرف B را باور نکن ، او دروغ می گوید.
چه طبقه ای از افراد B و C هستند؟
این بار با دو نفر الف و ب ملاقات می کنید
- یا من دروغگو هستم ، یا ب حقیقت گو است.
چه طبقه ای از افراد B است.
یک بار در جزیره با دو نفر آشنا شدم و از یکی از آنها پرسیدم:
- آیا یکی از شما راستگو است؟
با پاسخ او توانستم راه حل سوال خود را بدانم. چه طبقه ای از مردم بودند؟
سه نفر ، A ، B و C به جرم قضاوت می شوند. هر یک از این افراد می توانستند از جزیره بیایند یا نمی توانند. به یاد بیاورید که همه کسانی که از این جزیره می آیند یا دروغگو هستند یا راستگو هستند. افرادی که از این جزیره نمی آیند ، عادی خوانده می شوند و ممکن است حقیقت را بگویند یا نگویند.راستگو است. مظنونان گفتند:
ج: "من بی گناه هستم."
ب: "این درست است."
C: "B از جزیره می آید."
این سوال المپیاد کامپیوتر سالهای خیلی قبل بوده
در یک جزیره k انساننما زندگی میکنند. این انساننماها دو گونهاند: عدهای راستگو هستند و به هر پرسش جواب درست میدهند. عدهای دیگر دروغگو هستند و به هر پرسش جواب نادرست میدهند.
اگر انسانی به این جزیره برود، میتواند با مطرح کردن پرسشهایی مانند پرسشهای زیر که جواب آنها بله یا خیر است، این دودسته را از هم تشخیص دهد.
به عنوان مثال، فرض کنید A راستگو و B دروغگو است. در این صورت، پرسشها و پاسخها میتواند به صورت زیر باشد:
پرسش از A: آیا B دروغگو است؟ جواب: بله
پرسش از A: آیا A و B دروغگو هستند؟ جواب: خیر
پرسش از B: آیا ۲+۲=۴ ؟ جواب: خیر
پرسش از B: آیا تو دروغگو هستی؟ جواب: خیر
n تبهکار به این جزیره فرار کردهاند. این افراد تبهکار، در پاسخ به هر پرسش هر طور که بخواهند جواب میدهند، یعنی گاهی جواب درست و گاهی جواب نادرست میدهند.
کارآگاهی وظیفه دارد به این جزیره رفته و با مطرح کردن پرسشهایی نظیر پرسشهای فوق (فقط با جواب بله یا خیر) این تبهکاران را شناسایی و بازداشت کند.
فرض کنید که تبهکاران و انساننماها از نظر شکل ظاهری تفاوتی ندارند ولی یکدیگر را خوب میشناسند و میدانند که هر کدام از چه گروهی (راستگو، دروغگو یا تبهکار) هستند. همچنین میدانیم کارآگاه از قبل اطلاعی در مورد اینکه هر یک از ساکنین این جزیره از کدام گروه است، ندارد.
الف) ثابت کنید که اگر n=1 و k≥2، کارآگاه میتواند فرد تبهکار را شناسایی کند.
ب) ثابت کنید که در حالت کلی اگر k>n، کارآگاه میتواند افراد تبهکار را شناسایی کند.
ج) ثابت کنید که اگر k≤n، کارآگاه نمیتواند افراد تبهکار را شناسایی کند. یعنی افراد تبهکار میتوانند طوری به پرسشهای کارآگاه جواب دهند که کارآگاه هیچگاه نتواند مطمئن شود که یک فرد، تبهکار است.