المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۰

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

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

پاسخ

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

شکل سوال به صورت زیر قابل ترسیم است:

هیچ‌کدام از نقطه‌های بخش $A$ نمی‌توانند با هیچ‌یک از نقطه‌های بخش $B$ هم‌رنگ باشند.(چرا؟) دو نقطه‌ی $b$ و $c$ را در بخش $A$ و نقطه‌ی $a$ را در بخش $B$ می‌گذاریم. پس حداکثر اختلاف تعداد بخش(رنگ)ها $7-4=3$ می‌شود.


ابزار صفحه