Processing math: 0%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

از هر کدام از هفت نفر به‌نام‌های ‎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 دروغ گفته است.


ابزار صفحه