المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

یک گروه «انسان‌نما» شامل ۵ میمون است که بین هر دو میمون رابطه‌ی «دوستی» یا «دشمنی» برقرار است. این رابطه دو طرفه است٬ یعنی اگر $a$ با $b$ دوست (یا دشمن) باشد٬ $b$ هم با $a$ دوست (یا دشمن) است. هم‌چنین می‌دانیم که دوستِ دوست یک میمون و نیز دشمنِ دشمنِ او حتماً دوست اوست. چند گروه انسان‌نمای مختلف موجود است؟ توجه کنید که میمون‌های این گروه از هم متفاوت نیستند!

  1. ۱
  2. ۲
  3. ۳
  4. ۴
  5. ۸

پاسخ

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

دوستی بین دو میمون را با خط پررنگ و دشمنی بین آن‌ها را با خط کم‌رنگ نشان می‌دهیم که به شکل مقابل خواهیم رسید٬ با این توضیح که قرار است تعدادی از ۱۰ خط کشیده شده پر رنگ و مابقی کم‌رنگ شوند و در ضمن نمی‌توان در آن شکل مثلث‌هایی به شکل و یا ترسیم کرد

  1. اگر هر پنج ضلع پنج ضلعی پررنگ باشند٬ آن‌گاه تمام قطرهای آن پنج ضلعی نیز پررنگ خواهد شد و به شکل مقابل خواهیم رسید:
  2. اگر ضلعی مانند $cd$ از پنج ضلعی کم‌رنگ باشد آن‌گاه دقیقا یکی از دو ضلع $ec$ و $ed$ کم‌رنگ خواهند بود. اگر سه ضلع کم‌رنگ همگی متصل به یک ر‌اس(مانند $d$) متصل باشند و یا دو تا از آن‌ها به یک راس و سومی به راس دیگر وصل باشند به ترتیب به دو شکل «۱» و «۲» خواهیم رسید:

بقیه پاره‌خط‌های مربوط به اشکال فوق به‌صورت منحصربه‌فرد٬ به شکل زیر معلوم می‌شوند:


ابزار صفحه