المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

به چند طریق می‌توان پاره‌خط‌های شکل مقابل را رنگ‌آمیزی کرد به‌گونه‌ای که هر دو پاره‌خط که در یک نقطه‌ی انتهایی اشتراک دارند ناهمرنگ باشند؟ پاره‌خط‌ها را می‌توان با رنگ‌های قرمز، آبی و سبز رنگ‌آمیزی کرد و برای رنگ‌آمیزی پاره‌خط‌های متصل به رأس ‎$a$‎ می‌توان از رنگ زرد نیز استفاده کرد.

  1. صفر
  2. ۱
  3. ۴
  4. ۱۲
  5. ۲۴

پاسخ

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

به خاطر تقارن موجود در شکل اگر فرض کنیم $ab$ زرد، $ag$ قرمز، $ae$ آبی و $ad$ سبز باشند٬ کلیت مسئله به هم نمی‌خورد. در این صورت رنگ سایر یال‌ها به اجبار به شکل زیر خواهند بود:

$=de$قرمز ، $=ef$سبز ، $=dc$آبی ، $=fg$آبی ، $=cf$قرمز ، $=cb$سبز ، $=gb$؟

همان‌طور که مشخص است برای $gb$ رنگی پیدا نمی‌شود.


ابزار صفحه