Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۱:سوال ۱۴

سوال ۱۴

از هر کدام از هفت نفر به‌نام‌های F،E،D،C،B،A‎ و G‎ سؤال شد که چند نفر از بقیه را از قبل می‌شناسد. این افراد به‌ترتیب از A پاسخ دادند: ۲٬۲٬۳٬۴٬۵٬۶ و ۱ (یعنی به‌عنوان مثال ‎C، ‎۴‎ نفر دیگر را می‌شناسد). می‌دانیم:

  • حداکثر یک نفر دروغ گفته است.
  • دروغ‌گو تعداد افرادی که از قبل می‌شناسد را ‎کم‌تر از مقدار واقعی می‌گوید.
  • شناختن یک رابطه‌ی دوطرفه است.
  • F حتماً راست گفته است.

چه کسی حتماً دروغ گفته است؟

  1. D‎ یا E
  2. E یا G
  3. C یا G
  4. E‎ یا C
  5. D یا G

پاسخ

گزینه (۲) درست است.

یک نفر حداکثر ۶ نفر می‌تواند آشنا داشته باشد. بنابراین A حتما راست گفته است؛ یعنی A با همه دست داده است٬ از جمله G‎ و B نمی‌تواند دروغ گفته باشد زیرا در این صورت با ۶ نفر دست داده است( با همه) که در این صورت G‎ با هر دو نفر A و B دست داده است و جواب او «۱» دروغ است٬ در صورتی که تعداد دروغ‌گوها بیش از یک نفر نیست. پس B نیز راست‌گو می‌باشد؛ یعنی A باهمه و B به غیر از G‎ با همه دست داده‌اند. بنابراین E و F هر دو حداقل با هر دو نفر A و B دست داده‌اند. به طریق مشابه استدلال می‌شود که دو نفر C و D‎ نمی‌توانند دروغ‌گو باشند یعنی یکی از دو نفر E یا G دروغ گفته است.


ابزار صفحه