سوال ۱۴
از هر کدام از هفت نفر به‌نام‌های $F، E ،D، C، B، A$ و $G$ سؤال شد که چند نفر از بقیه را از قبل می‌شناسد. این افراد به‌ترتیب از $A$ پاسخ دادند: ۲٬۲٬۳٬۴٬۵٬۶ و ۱ (یعنی به‌عنوان مثال $C$، ۴ نفر دیگر را می‌شناسد). می‌دانیم:
- حداکثر یک نفر دروغ گفته است.
- دروغ‌گو تعداد افرادی که از قبل می‌شناسد را کم‌تر از مقدار واقعی می‌گوید.
- شناختن یک رابطه‌ی دوطرفه است.
- $F$ حتماً راست گفته است.
چه کسی حتماً دروغ گفته است؟
- $D$ یا $E$
- $E$ یا $G$
- $C$ یا $G$
- $E$ یا $C$
- $D$ یا $G$
پاسخ
گزینه (۲) درست است.
یک نفر حداکثر ۶ نفر می‌تواند آشنا داشته باشد. بنابراین $A$ حتما راست گفته است؛ یعنی $A$ با همه دست داده است٬ از جمله $G$ و $B$ نمی‌تواند دروغ گفته باشد زیرا در این صورت با ۶ نفر دست داده است( با همه) که در این صورت $G$ با هر دو نفر $A$ و $B$ دست داده است و جواب او «۱» دروغ است٬ در صورتی که تعداد دروغ‌گوها بیش از یک نفر نیست. پس $B$ نیز راست‌گو می‌باشد؛ یعنی $A$ باهمه و $B$ به غیر از $G$ با همه دست داده‌اند. بنابراین $E$ و $F$ هر دو حداقل با هر دو نفر $A$ و $B$ دست داده‌اند. به طریق مشابه استدلال می‌شود که دو نفر $C$ و $D$ نمی‌توانند دروغ‌گو باشند یعنی یکی از دو نفر $E$ یا $G$ دروغ گفته است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
