المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۵۶

سوال ۵۶

می‌خواهیم به هر یک از رئوس ۵ ـ ضلعی زیر یک رنگ از سه رنگ $b،a$ یا $c$ را نسبت دهیم به طوری که رئوس دو سر یک ضلع هم‌رنگ نباشند. می‌دانیم که این رنگ‌آمیزی را می‌توان به صورت‌های مختلف انجام داد. حال می‌خواهیم برای رنگ‌آمیزی «محدودیت» ایجاد کنیم. هر محدودیت شامل یک شماره‌ی راس و یک رنگ است و معنی آن٬ این است که راس مذکور نمی‌تواند با آن رنگ٬ رنگ‌آمیزی شود.

آیا می‌توان ۵ محدودیت برای این شکل ایجاد کرد به قسمی که با رعایت آن‌ها رئوس ۵ ـ ضلعی دقیقا به یک صورت رنگ‌آمیزی شود؟

پاسخ

محدودیت‌های لازم می‌تواند به شکل $(3,c)،(2,a)،(1,b)،(1,a)$ و $(4,c)$ باشد.


ابزار صفحه