اتاقی به شکل یک $n$ ضلعی ساده با اضلاع موازی محورهای مختصات داریم. می خواهیم آن را با تعدادی فرش مستطیل‌شکل بپوشانیم، به طوری که هیچ دوفرشی هم‌پوشانی نداشته باشند و تمام فضای اتاق پوشیده شود.

1. فرض کنید هیچ دونقطه ای هم $x$ یا هم $y$ نیستند، مگراین‌که دو سر یک ضلع باشند. تعداد مستطیل‌های لازم برای پوشاندن اتاق را با فرمولی صریح بر حسب $n$ بدست آورید.
2. الگوریتمی از $O(n^3)$ برای پیداکردن تعداد مستطیل‌های لازم ارائه دهید.
3. حال فرض کنید ممکن است در اتاق ستون هایی به شکل مستطیل با اضلاع موازی محور $x$ و $y$ مختصات داریم، طوری که هیچ کدام از ستون ها با دیواره اتاق برخوردی ندارند.

• سوال قبل