شکل زیر، یک جدول $5 \times 5$ با حذف چهار گوشهی آن است. میخواهیم این شکل را به طور کامل با کاشیهای $1 \times 1$، $2 \times 2$ و $3 \times 3$ بپوشانیم، طوری که کاشیها روی هم قرار نگرفته و از جدول بیرون نزنند. نیازی نیست از هر سه نوع کاشی استفاده کنیم. حداقل تعداد کاشیها برای انجام این کار چیست؟
پاسخ
گزینهی ۱ درست است.
روش پرکردن با ۹ کاشی:
حال ثابت میکنیم با کمتر از ۹ کاشی امکان پر کردن جدول وجود ندارد. حداکثر یک کاشی $3 \times 3$ میتوانیم داشته باشیم. اگر کاشی $3 \times 3$ نداشته باشیم، هر کاشی حداکثر یک خانهی مشخص شده در شکل زیر را میپوشاند و دست کم به ۹ کاشی نیاز داریم:
اگر کاشی $3 \times 3$ داشته باشیم و این کاشی در وسط جدول باشد، بقیهی جدول باید با کاشیهای $1 \times 1$ پر شوند که دست کم به ۱۳ کاشی نیاز داریم. اگر هم کاشی $3 \times 3$ داشته باشیم ولی در وسط جدول نباشد، شش خانه به طور یکتا با $1 \times 1$ پر میشوند و یک جدول $2 \times 3$ میماند که خودش دست کم به سه کاشی نیاز دارد. پس این حالت نیز دست کم $1+6+3=10$ میخواهد.