سوال ۱۰
در ساعت صفر، ۱۰ نفر با شماره‌های ۱ تا ۱۰ برای پر کردن سطل خود در مقابل یک شیر آب صف کشیده‌اند. به محض این که سطل فردی که در جلوی شیر آب است پر می‌شود، او به کنار می‌رود و نفر بعدی در صف جای او را می‌گیرد. فرض کنید سطل نفر $i$ام به اندازه‌ای است که پر کردن آن $i$ دقیقه طول می‌کشد. زمانی که نفر $i$ام سطل خود را پر می‌کند را «زمان معطلی» نفر $i$ام می‌نامیم. کدام‌یک از گزینه‌های زیر درباره‌ی مجموع زمان معطلی ۱۰ نفر درست است؟
- افراد می‌توانند به ترتیبی در صف بایستند که مجموع زمان‌های معطلی می‌تواند کم‌تر از ۳/۵ دقیقه باشد.
- افراد می‌توانند به ترتیبی در صف بایستند که مجموع زمان‌های معطلی می‌تواند بیش‌تر از ۷ دقیقه باشد.
- اگر افراد به ترتیب شماره‌هایشان(نفر ۱ اول) در صف بایستند مقدار مجموع زمان‌های معطلی کمینه است.
- اگر افراد به ترتیب عکس شماره‌هایشان(نفر ۱ آخر) در صف بایستند مقدار مجموع زمان‌های معطلی کمینه است.
- به هر ترتیبی که افراد در صف بایستند مجموع زمان‌های معطلی تغییر نخواهد کرد.
پاسخ
گزینه (۳) درست است.
اگر افراد به ترتیب شماره‌هایشان در صف قرار گیرند آن‌گاه مجموع زمان‌های معطلی برابر:
$$10\times1+9\times2+8\times3+...+1\times10$$
یعنی ۲۱۸ دقیقه و اگر به ترتیب عکس شماره‌هایشان در صف قرار گیرند آن‌گاه مجموع زمان‌های معطلی برابر:
$$10\times10+9\times9+8\times8+...+1\times1$$
یعنی ۳۸۵ دقیقه خواهد بود. حالت اول حداقل مجموع زمان‌های معطلی را دارد زیرا اگر نفر $i$ ام بعد از نفر $j$ ام ($i<j$) در صف قرار گیرند با جابه‌جایی آن دو نفر مجموع کل معطلی به اندازه‌ی $j-i$ دقیقه کاهش می‌یابد. به همین ترتیب ثابت می‌شود که حالت دوم نیز حداکثر مجموع زمان‌های معطلی را دارد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
