المپدیا

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

ابزار کاربر

ابزار سایت


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

عمو نقاش

دیوار خانه‌ی عمو نقّاش به صورت یک جدول $n \times n$ می‌باشد. عمو نقّاش برای این‌که مصداق ضرب‌المثل «کوزه‌گر از کوزه‌شکسته آب می‌خورد» نشود٬ می‌خواهد دیوار خانه‌اش را رنگ‌آمیزی کند. برای این‌ کار عمو هر بار قلم‌موی خودش را درون یک سطل رنگ متفاوت با رنگ‌های قبلی که تا به حال استفاده کرده٬ می‌کند و قلم‌موی رنگی را روی یک سطل یا یک ستون جدول به طور کامل می‌کشد.

عمو نقّاش می‌خواهد هر کسی به خانه‌شان می‌آید٬ هنرش را بفهمد. به همین خاطر او می‌خواهد طوری دیوار را رنگ‌آمیزی کند که تعداد رنگ‌هایی که روی دیوار دیده می‌شود٬ بیش‌ترین باشد.

شما به عمو نقّاش کمک کنید٬ به این معنی که اولاً٬ برای هر عدد $n$٬ یک روش رنگ‌آمیزی ارائه دهید که در آن با بیش‌ترین تعداد رنگ دیوار رنگ‌آمیزی شود و ثانیاً٬ ثابت کنید این مقدار بیشینه است.


ابزار صفحه