Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۵

nنفر دور میزی دایره‌ای شکل نشسته‌اند. هر نفر یا راستگوست یا دروغگو (راست‌گو همیشه راست و دروغ‌گو همیشه دروغ می‌گوید). هرکدام از این n نفر این جمله را می‌گوید: « بین من و دو نفرِ سمت ِ راست و دو نفرِ سمتِ چپِ من، دقیقاً k نفر دروغ‌گو هستند.» کدام‌یک از گزاره‌های زیر در مورد r، تعدادِ حالاتِ دروغ‌گو و راست‌گو بودنِ این افراد، درست است؟

  1. اگر n=۵۱ و k=۴، آنگاه r=۴.
  2. اگر n=۵۰ و k=۰، آنگاه r=۰.
  3. اگر n=۵۱ و k=۵، آنگاه r=۱.
  4. اگر n=۵۰ و k=۱، آنگاه r=۶.
  5. اگر n=۵۲ و k=۱، آنگاه r=۶.

پاسخ

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

  1. n=51 و k=۴. اگر هیچ یک از افراد راست‌گو نباشند و همه افراد دروغگو باشند٬ آن‌گاه جمله مورد نظر در مورد همه‌ی افراد مصداق پیدا می‌کند. اگر فردی مانند d راست‌گو باشد٬ آن‌گاه برای آن‌که جمله داده شده مصداق داشته باشد باید هر چهار نفر b،c،e و f دروغ‌گو باشند که در این صورت نیز برای آن‌که جمله مورد نظر در مورد دروغ‌گو‌ها مانند e مصداق داشته باشد٬ باید g راست‌گو باشد. بنابراین در این حالت از هر سه نفر متوالی دو نفر دروغ‌گو و یک نفر راست‌گوست( یعنی به صورت…رددرددردد…)و تعداد جای‌گشت‌ها در این مورد برابر ۳ است. باتوجه به حالت‌بندی فوق در این قسمت r برابر ۴ به‌دست می‌آید که در صورت مسئله نیز ۴ داده شده است.
  2. n=۵۰ و k=۰. اگر همه ۵۰ نفر راست‌گو باشند این حالت اتفاق می‌افتد بنابراین در این قسمت مقدار r برابر ۱ در می‌آید در حالی که برابر ۰ داده شده است.
  3. n=۵۱ و k=۵. معلوم است که این حالت هرگز اتفاق نخواهد افتاد زیرا اگر حتی یک نفر راست‌گو در بین افراد باشد جمله داده شده در مورد او مصداق نخواهد داشت و اگر همه دروغ‌گو باشند نیز جمله یاد شده در مورد آن‌ها مصداق نخواهد داشت. بنابراین در این قسمت مقدار r برابر ۰ می‌شود در حالی که در صورت مسئله این عدد برابر ۱ داده شده است.
  4. n=۵۰ و k=۱. تنها حالت ممکن آ» است که همه دروغ‌گو باشند٬ بنابراین r=۱ در حالی که در صورت مسئله r برابر ۶ داده شده است.
  5. n=۵۲ و k=۱. در این قسمت نیز تنها حالت ممکن آن است که همه دروغ‌گو باشند٬‌ بنابراین r=۱ و در حالی که در صورت مسئه r برابر ۶ داده شده است.

ابزار صفحه