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