محمد ۱۳ قاب چوبی به شکل مربع دارد که حاشیه‌ی هر کدام ۲ سانتی‌متر عرض دارد. طول ضلع قاب های محمد به ترتیب ۲۵٫۲۳٫۲۲٫۲۱٫۱۸٫۱۵٫۱۳٫۱۲٫۱۱٫۷٫۶٫۵ و ۲۹ هستند. مثلا مساحت قاب به ضلع ۱۵ با توجه به حاشیه‌ي داخلی برابر با ۱۲۱ سانتی متر مربع است.
محمد می خواهد حداقل ۴ تا از این قاب ها را برای اسباب‌کشی انتخاب کند. او می خواهد این قاب ها را طوری انتخاب کند که اولا همگی درون هم بروند (قاب به ضلع ۲۵ دقیقا درون قاب به ضلع ۲۹ می رود) ؛ ثانیا مساحت فضای خالی درون قاب ها که او حمل می کند (مساحت درونی خارجی ترین قاب منهای مساحت چوب های حاشیه های قاب های داخلی) کمینه بشود! این میزان کمینه کدام است؟
دقت کنید که درون هر قاب (به جز داخلی ترین قاب) دقیقا یک قاب باید مستقیما برود و هر قاب (به جز خارجی ترین قاب) هم می بایست به طور مستقیم دقیقا درون یک قاب دیگر باشد.
پاسخ
گزینه‌ی «۱» درست است.
واضح است که تلاش می‌کنیم درونی ترین قاب تا جای ممکن کوچک باشد، پس بهتر است از درونی ترین قاب شروع کنیم. می‌گوییم بهترین حالت این است که 5 درونی ترین باشد. حال بیرون آن کوچک‌ترین قابی که می‌توانیم بگذاریم 11 است، پس بهتر است به‌جای 5، 7 را بگذاریم. سپس بیرون 7، 11 ، 15 را می‌توان بگذاریم بدون این‌که فضای اضافی ایجاد شود اما بعد از آن باید 21 را بگذاریم که با محاسبه می‌فهمیم که در این حالت 73 واحد خالی مانده.
اما می‌توانیم بجای15، 18 را نیز بگذاریم و به‌جای 21 نیز 22. سپس به‌جای 11 نیز 13 را می‌گذاریم.
یعنی این دنباله : 7، 13 ، 18، 22. با محاسبه فضای خالی این قاب‌ها به عدد 68 می‌رسیم. با کمی بررسی حالت های دیگر درمی‌یابیم که این بهترین جواب است.