المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

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

  1. می‌توان نقاط را با ۳ رنگ٬ رنگ‌آمیزی کرد
  2. می‌توان نقاط را با ۴ رنگ٬ رنگ‌آمیزی کرد
  3. با حذف هر پاره‌خط٬ نقاط را می‌توان با ۳ رنگ٬ رنگ‌آمیزی کرد
  4. گزینه‌های ۱ و ۲ و ۳
  5. گزینه‌های 2 و ۳

پاسخ

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

سه راس $d ، a$ و $e$ سه رنگ متمایز دارند و نیز سه راس $d ، g$ و $e$ نیز سه رنگ متمایز دارند٬ بنابراین اگر بخواهیم رئوس را فقط با سه رنگ٬ رنگ‌آمیزی کنیم آن‌گاه $a$ و $g$ هم‌رنگ خواهند بود. به همین ترتیب معلوم می‌شود که $a$ و $f$ هم‌رنگ هستند که در این صورت دو راس $f$ و $g$ که به هم وصل هستند هم‌رنگ شده و با فرض داده شده تناقض ایجاد می‌کند.

شکل داده شده را با ۴ نوع رنگ به شکل زیر می‌توان رنگ کرد:

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ آبی:$b,e$ $\quad\quad\quad\quad\quad\quad$ سبز: $a,g$

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$ زرد:$f$ $\quad\quad\quad\quad\quad\quad$ قرمز: $d,c$

و همچنین قابل بررسی است که با حذف هر یال رنگ‌آمیزی شکل با سه رنگ امکان‌پذیر است.


ابزار صفحه