المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۳:سوال ۱۱

سوال ۱۱

یک جدول $۱۰\times۱۰$ داریم. می خواهیم تعدادی از خانه های آن را رنگ کنیم به طوری که شرط زیر برقرار باشد:

  • به ازای هر پوشش این جدول با مستطیل های $۱\times۲$، تعداد مستطیل های $۱\times۲$ که هر دو خانه ی آن ها رنگ شده است حداکثر ۲۵ باشد.

توجه کنید که در هر پوشش باید هر خانه ی جدول توسط دقیقا یک مستطیل $۱\times۲$ پوشانده شود. همچنین مستطیل های $۱\times۲$ می توانند به صورت افقی یا عمودی قرار بگیرند و هرکدام باید دقیقا دو خانه را پوشش دهند. با این شرایط حداکثر چند خانه را می توانیم رنگ کنیم؟

  1. ۵۱
  2. ۵۰
  3. ۸۰
  4. ۶۰
  5. ۷۵

پاسخ

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

در صورتی که در یک پوشش ۲۵ مستطیل کامل رنگ شده باشد و از بقیه‌ی مستطیل‌ها نیز حداکثر یک خانه‌ی رنگ شده داشته باشیم، به حداکثر ۷۵ خانه‌ی رنگی خواهیم داشت.

مثال زیر با این تعداد رنگ‌آمیزی، شرایط مسئله را برآورده کرده است.


ابزار صفحه