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

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

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

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