المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

یک دومینو، یک مستطیل ‎$2\times1$‎ یا ‎$1\times2$‎ است که از دو مربع ‎$1\times1$‎ به‌هم چسبیده تشکیل شده است. تعدادی دومینو را در یک جدول ‎$n\times m$‎ خانه‌ای قرار داده‌ایم به‌طوری که هر کدام روی دقیقاً ‎۲‎ تا از خانه‌های جدول هستند و هیچ دو دومینویی روی هم نیافتاده‌اند. توجه کنید که دومینو ها لزوماً همه‌ی جدول را پر نکرده‌اند‎!‎

ثابت کنید می‌توان دومینوهای موجود در جدول را طوری با ‎۴‎ رنگ، رنگ کرد که هیچ دو دومینوی مجاوری (که در بیش از یک نقطه با هم اشتراک دارند)، هم‌رنگ نباشند.


ابزار صفحه