المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۹:سوالات ۲۴ و ۲۵

سوالات ۲۴ و ۲۵

گروهی از افراد با هم قرار گذاشته‌اند که رأس هر ساعت هر کدام خبرهایی که در ساعت قبل دریافت کرده است برای همه‌ی دوستان خود بفرستد. در یک \متن‌سیاه{شبکه‌ی دوستی}، هر فرد با یک دایره نشان داده می‌شوند و اگر دو نفر با هم دوست باشند، دایره‌های آن‌ها به هم وصل می‌شوند. شکل زیر یک شبکه‌ی دوستی با سه نفر را نشان می‌دهد. در این شبکه اگر ابتدا نفر ۱ خبر جدیدی را دریافت کند، نفر ۲ پس از یک ساعت و نفر ۳ پس از دو ساعت از آن خبر مطلع می‌شود؛ در حالی که اگر نفر ۲ اولین کسی باشد که خبر را دریافت می‌کند، پس از یک ساعت همه از خبر مطلع می‌شوند.

سوال ۲۴

یک شبکه‌ی دوستی در شکل زیر آمده است. در این شبکه، یک خبر جدید را ابتدا به چه کسی بدهیم تا در کم‌ترین زمان ممکن خبر به همه برسد؟

  1. ۲
  2. ۴
  3. ۷
  4. ۱۰
  5. ۱۳

پاسخ

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

اگر به یکی از افراد گوشه خبر داده شود، در ۴ ساعت خبر منتشر می‌شود. اگر یکی از افراد ۴، ۵ و یا ۶ خبر را دریافت کند، در ۶ ساعت خبر منتشر می‌شود. اگر خبر برای اولین بار به افراد دیگر برسد، در ۵ ساعت پخش می‌شود. پس جواب می‌تواند هر کدام از افراد گوشه‌ای (۱، ۲ و یا ۳) باشد.

سوال ۲۵

در شبکه‌ی دوستی زیر، یک خبر جدید را به کدام دو نفر بدهیم تا در کم‌ترین زمان ممکن خبر به همه برسد؟

  1. ۲ و ۵
  2. ۴ و ۱۶
  3. ۵ و ۱۲
  4. ۷ و ۱۹
  5. ۱۷ و ۱۹

پاسخ

گزینه‌ی ۲ درست است.

این شبکه مربوط به یک دوازده‌وجهی است و کاملاً متقارن است. اگر دو رأسی که از هم دور هستند و فاصله‌ی ۵ دارند را انتخاب کنیم، در ۲ ساعت خبر پخش می‌شود و اگر دو رأس فاصله‌ی کمتری داشته باشند جواب بیش‌تر از ۲ است. در بین گزینه‌ها فقط ۴ و ۱۶ این خاصیت را دارند.


ابزار صفحه