المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:تئوری:سوال ۴

جدول رنگارنگ

می‌خواهیم خانه‌های یک جدول $m\times n$ را با $k$ رنگ، رنگ‌آمیزی کنیم. یک ضلع داخلی جدول را رنگی می‌نامیم اگر دو طرف آن، دو رنگ متفاوت باشند. ثابت کنید حداقل به $\binom{mn-2}{k-2}$ روش مختلف می‌توان جدول را رنگ کرد به طوری که تعداد ضلع‌های رنگی آن، ماکسیمم باشد.


ابزار صفحه