المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۷:سوالات ۲۹ و ۳۰

سوالات ۲۹ و ۳۰

در منطقه‌ای در نزدیکی شهر لندن، قتلی توسط سه نفر اتّفاق افتاده است. سلطان به سرعت وارد عمل شد و پنج متّهم ($A$، $B$، $C$، $D$، $E$) را دست‌گیر کرد. هر یک از آن‌ها ادّعا کرد که قاتل نیست، ولی نام دو نفر از چهار نفر دیگر را به عنوان کسانی که به احتمال زیاد قاتل هستند، به زبان آورد. سلطان متوجّه شد که هر یک از قاتل‌ها برای رد گم کردن، نام دقیقن یک قاتل دیگر را بر زبان آورده است و هر یک از بی‌گناهان نیز نام دو قاتل را گفته است. در هر یک از حالت‌های زیر مشخص کنید سلطان چند نفر را به طور قطع می‌تواند قاتل معرفی کند؟

سوال ۲۹

اظهارات:

  • $A$: $B$و $C$ قاتل هستند.
  • $B$: $A$و $C$ قاتل هستند.
  • $C$: $B$و $E$ قاتل هستند.
  • $D$: $E$و $C$ قاتل هستند.
  • $E$: $B$و $D$ قاتل هستند.
  1. ۰
  2. چنین چیزی ممکن نیست
  3. ۲
  4. ۱
  5. ۳

پاسخ

گزینه‌ی ۵ درست است.

حتمن $C$ قاتل است. فرض کنید چنین نباشد. در این صورت $A$، $B$ و $D$ قاتل هستند، زیرا ادّعا کرده‌اند $C$ قاتل است. $E$ نیز باید قاتل باشد، زیرا $C$ چنین ادّعایی دارد. پس چهار قاتل داریم که تناقض است. تناقض حاصل ثابت می‌کند که $C$ باید قاتل باشد.

حال ثابت می‌کنیم $B$ نیز حتمن قاتل است. فرض کنید چنین نباشد. در این صورت $A$، $C$ و $E$ باید قاتل باشند، زیرا ادّعا کرده‌اند $B$ قاتل است. پس $D$ نباید قاتل باشد، زیرا سه قاتل دیگر تا کنون مشخص شده است. حال در ادّعای $E$ هیچ قاتلی وجود ندارد که امکان ندارد. تناقض حاصل ثابت می‌کند که $B$ باید قاتل باشد.

با توجه به اظهارات درست $A$، می‌فهمیم که او قاتل نیست. با توجه به اظهارات $C$ می‌فهمیم $E$ قاتل نیست. پس قاتل سوم ($D$) نیز مشخّص می‌شود.

پس وضعیّت همه مشخّص شد و پاسخ برابر ۳ است.

سوال ۳۰

اظهارات:

  • $A$: $B$و $C$ قاتل هستند.
  • $B$: $A$و $C$ قاتل هستند.
  • $C$: $B$و $A$ قاتل هستند.
  • $D$: $E$و $B$ قاتل هستند.
  • $E$: $C$و $D$ قاتل هستند.
  1. ۲
  2. ۳
  3. ۰
  4. چنین چیزی ممکن نیست
  5. ۱

پاسخ

گزینه ۱ درست است.

حتمن $C$ قاتل است. فرض کنید چنین نباشد. در این صورت $A$، $B$ و $E$ قاتل هستند، زیرا ادّعا کرده‌اند $C$ قاتل است. $D$ قاتل نیست، زیرا تا کنون سه قاتل دیگر پیدا کرده‌ایم. در اظهارات $E$ هیچ قاتلی نیست که امکان ندارد. تناقض حاصل ثابت می‌کند که $C$ باید قاتل باشد.

به استدلال مشابه $B$ نیز قاتل است. با توجه به اظهارات درست $A$ او قاتل نیست. حال هر کدام از $D$ و $E$ می‌توانند قاتل سوم باشند. پس پاسخ برابر ۲ است.


ابزار صفحه