فهرست مندرجات
سوالات ۲۴ و ۲۵
گروهی از افراد با هم قرار گذاشته‌اند که رأس هر ساعت هر کدام خبرهایی که در ساعت قبل دریافت کرده است برای همه‌ی دوستان خود بفرستد. شبکه‌ی دوستی، هر فرد با یک دایره نشان داده می‌شوند و اگر دو نفر با هم دوست باشند، دایره‌های آن‌ها به هم وصل می‌شوند. شبکه ای را در نظر بگیرید که دایره ۱ به دایره ۲ وصل است و دایره ۲ به دایره ۳. در این شبکه اگر ابتدا نفر ۱ خبر جدیدی را دریافت کند، نفر ۲ پس از یک ساعت و نفر ۳ پس از دو ساعت از آن خبر مطلع می‌شود؛ در حالی که اگر نفر ۲ اولین کسی باشد که خبر را دریافت می‌کند، پس از یک ساعت همه از خبر مطلع می‌شوند.
سوال ۲۴
یک شبکه‌ی دوستی در شکل زیر آمده است. در این شبکه، یک خبر جدید را ابتدا به چه کسی بدهیم تا در کم‌ترین زمان ممکن خبر به همه برسد؟
- ۲
- ۴
- ۷
- ۱۰
- ۱۳
راهنمایی
افراد گوشه به طور متقارن باهم خبر را پخش می کنند، اگر به یکی از آن ها خبر را بدهیم در چند ساعت پخش میکنند؟
پاسخ
گزینه‌ی ۱ درست است.
اگر به یکی از افراد گوشه خبر داده شود، در ۴ ساعت خبر منتشر می‌شود. اگر یکی از افراد ۴، ۵ و یا ۶ خبر را دریافت کند، در ۶ ساعت خبر منتشر می‌شود. اگر خبر برای اولین بار به افراد دیگر برسد، در ۵ ساعت پخش می‌شود. پس جواب می‌تواند هر کدام از افراد گوشه‌ای (۱، ۲ و یا ۳) باشد.
سوال ۲۵
در شبکه‌ی دوستی زیر، یک خبر جدید را به کدام دو نفر بدهیم تا در کم‌ترین زمان ممکن خبر به همه برسد؟
- ۲ و ۵
- ۴ و ۱۶
- ۵ و ۱۲
- ۷ و ۱۹
- ۱۷ و ۱۹
راهنمایی
دو نفری را انتخاب کنید که دور ترین فاصله را از هم دارند
پاسخ
گزینه‌ی ۲ درست است.
این شبکه مربوط به یک دوازده‌وجهی است و کاملاً متقارن است. اگر دو رأسی که از هم دور هستند و فاصله‌ی ۵ دارند را انتخاب کنیم، در ۲ ساعت خبر پخش می‌شود و اگر دو رأس فاصله‌ی کمتری داشته باشند جواب بیش‌تر از ۲ است. در بین گزینه‌ها فقط ۴ و ۱۶ این خاصیت را دارند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
