المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۳

هر سال، نهنگی که متوجه شود یکی از نهنگ‌هایی که او دوست داشته، سال گذشته مرده، خودکشی می‌کند. شکل روبه‌رو یک جامعه از نهنگ‌ها را نشان می‌دهد. اگر نهنگ $A$ به $B$ پیکان داشته باشد، یعنی $A$٬ $B$ را دوست دارد. حدّاقل چند پیکان جدید باید رسم کنیم تا نهنگی وجود داشته باشد که با کشتن آن، همه‌ی نهنگ‌ها از بین بروند؟

  1. ۲
  2. ۳
  3. ۴
  4. ۵
  5. هیچ‌کدام

پاسخ

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

نهنگ‌هایی که کسی را دوست ندارند (به کسی یال ندارند) در هر صورت خودکشی نمی‌کنند، پس هرکدام از این نهنگ‌ها باید یک نهنگ دیگر را دوست داشته باشد. نهنگ‌های 2، 3 و 4 به هیچ نهنگی پیکان ندارند پس حتی اگر یکی از این نهنگ‌هارا نیز در ابتدا بکشیم دو نهنگ دیگر باید یک پیکان خروجی داشته باشند تا خودکشی کنند.

اگر دو پیکان از نهنگ‌های 3و 4 به نهنگ 2 بکشیم، بعد از کشتن نهنگ 2، همه‌ی نهنگ‌ها بعد از چند مرحله خودکشی می‌کنند .


ابزار صفحه