المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۹:سوال ۸

سوال ۸

هشت شایعه‌ساز داریم که گراف آشنایی آن‌ها به شکل زیر است (آشنایی را رابطه‌ای دوطرفه در نظر بگیرید):

هر شایعه‌ساز هر روز می‌تواند یکی از سه کار زیر را انجام دهد:

  1. استراحت کند.
  2. یک شایعه‌ی جدید بسازد! در این صورت او به دلیل فشار کاری، روز بعد را باید استراحت کند.
  3. تمام شایعه‌هایی را که تا قبل از آن روز داشته (چه خودش ساخته باشد و چه از طریق آشنایانش گرفته باشد)، به تمام آشنایانش بگوید.

دریافت کردن شایعه‌های آشنایان، مستقل از سه حالت بالاست و حتی شایعه‌ساز در حال استراحت هم می‌تواند شایعه دریافت کند. به یک شایعه فراگیر گوییم، اگر تمام هشت نفر آن را بدانند. پس از ۱۶ روز حداکثر چند شایعه‌ی فراگیر متمایز وجود خواهد داشت؟

  1. $56$
  2. $112$
  3. $120$
  4. $60$
  5. $14$

پاسخ

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


ابزار صفحه