سوال ۸
هشت شایعهساز داریم که گراف آشنایی آنها به شکل زیر است (آشنایی را رابطهای دوطرفه در نظر بگیرید):
هر شایعهساز هر روز میتواند یکی از سه کار زیر را انجام دهد:
- استراحت کند.
- یک شایعهی جدید بسازد! در این صورت او به دلیل فشار کاری، روز بعد را باید استراحت کند.
- تمام شایعههایی را که تا قبل از آن روز داشته (چه خودش ساخته باشد و چه از طریق آشنایانش گرفته باشد)، به تمام آشنایانش بگوید.
دریافت کردن شایعههای آشنایان، مستقل از سه حالت بالاست و حتی شایعهساز در حال استراحت هم میتواند شایعه دریافت کند. بهیک شایعه فراگیر گوییم، اگر تمام هشت نفر آن را بدانند. پس از ۱۶ روز حداکثر چند شایعهی فراگیر متمایز وجود خواهد داشت؟
- 60
- 112
- 56
- 14
- 120
پاسخ
گزینه (3) درست است.
| ▸ سوال قبل | سوال بعد ◂ |
