المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۵

$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$ برابر ۶ داده شده است.

ابزار صفحه