کف یک اتاق مستطیل شکل را می‌خواهیم با تعدادی متناهی فرش بپوشانیم. تمام فرش‌ها مستطیل شکل‌اند و ابعادی حقیقی دارند. یک نقشه‌ی قابل قبول٬ نحوه‌ی قرار گرفتن هر فرش در اتاق را نشان می‌دهد به طوری که هر نقطه‌ی اتاق دقیقاً توسط یک فرش پوشانده شده باشد؛ یعنی فرش‌ها روی هم قرار نگرفته‌اند و هیچ جای اتاق خالی نیست. می‌دانیم در هر نقشه‌ی قابل قبول٬ ضلع‌های هر فرش موازی اضلاع اتاق خواهد بود.

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

مثلاً در زیر شکل (۱) یک نقشه‌ی قابل قبول است٬ و شکل (۲) آن یک ترتیب غیر خوب را نشان می‌دهد٬ چرا که هنگام اضافه شدن فرش شماره‌ی ۳ قسمتی از پایین این فرش هنوز پوشانده نشده است٬ که بعداً توسط فرش ۴ پوشانده می‌شود. شکل (۳) یک ترتیب خوب را نشان می‌دهد.

ثابت کنید که به ازای هر نقشه‌ی قابل قبول٬ یک ترتیب خوب وجود دارد.

• سوال بعد
• سوال قبل