المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۴:سوال ۵

سوال ۵

جدولی $n\times n$ در نظر بگیرید. به یک خانه از این جدول ناسازگار می‌گوییم اگر بتوان تمام خانه‌های جدول به جز این خانه را با بلوک‌های ۳ × ۱ پوشاند (بلوک‌ها نباید هم‌پوشانی داشته باشند و از جدول بیرون بزنند). برای n=۵ و n=۷ تعداد خانه‌های ناسازگار به ترتیب (از راست به چپ)‌ چند است‌؟

  1. ۱ و ۹
  2. ۱ و ۱۷
  3. ۹ و ۹
  4. ۹ و ۱۷
  5. ۹ و ۴۹

پاسخ

گزینه‌ی ۱ درست است.

جدول را به صورت متناوب و یک در میان با اعداد ۱ و ۲ و ۳ رنگ‌آمیزی کنید به طوری که هر بلوک که در جدول گذاشته‌ می‌شود، دقیقا یک خانه از هر رنگ را بپوشاند. مثلا برای جدول ۵ × ۵ این رنگ‌آمیزی به این صورت است:

حال اگر خانه‌ای ناسازگار باشد باید رنگ آن 1 باشد، زیرا تعداد خانه‌های به رنگ ۱ یکی از ۲ و ۳ بیش‌تر است. از طرفی هر خانه ای که سازگار باشد معادل آن خانه پس از چرخش ۹۰، ۱۸۰ و ۲۷۰ درجه‌ای جدول نیز باید ناسازگار باشد. تنها خانه‌ای که در جدول ۵ × ۵ این خاصیت را دارد، خانه‌ی وسطی است. برای جدول ۷ × ۷ نیز ۹ خانه این خاصیت را دارند.


ابزار صفحه