سوال ۱۰

در ساعت صفر، ‎۱۰‎ نفر با شماره‌های ‎۱‎ تا ‎۱۰‎ برای پر کردن سطل خود در مقابل یک شیر آب صف کشیده‌اند. به محض این که سطل فردی که در جلوی شیر آب است پر می‌شود، او به کنار می‌رود و نفر بعدی در صف جای او را می‌گیرد. فرض کنید سطل نفر ‎$i$‎ام به اندازه‌ای است که پر کردن آن ‎$i$‎ دقیقه طول می‌کشد. زمانی که نفر ‎$i$‎ام سطل خود را پر می‌کند را ‎«زمان معطلی»‎ نفر ‎$i$‎ام می‌نامیم. کدام‌یک از گزینه‌های زیر درباره‌ی مجموع زمان معطلی ‎۱۰‎ نفر درست است؟

  1. افراد می‌توانند به ترتیبی در صف بایستند که مجموع زمان‌های معطلی می‌تواند کم‌تر از ۳/۵ دقیقه باشد‎.
  2. افراد می‌توانند به ترتیبی در صف بایستند که مجموع زمان‌های معطلی می‌تواند بیش‌تر از ۷ دقیقه باشد‎.‎
  3. اگر افراد به ترتیب شماره‌هایشان(نفر ۱ اول) در صف بایستند مقدار مجموع زمان‌های معطلی کمینه است‎.‎
  4. اگر افراد به ترتیب عکس شماره‌هایشان(نفر ۱ آخر) در صف بایستند مقدار مجموع زمان‌های معطلی کمینه است‎.‎
  5. به هر ترتیبی که افراد در صف بایستند مجموع زمان‌های معطلی تغییر نخواهد کرد‎.

پاسخ

گزینه (۳) درست است.

اگر افراد به ترتیب شماره‌هایشان در صف قرار گیرند آن‌گاه مجموع زمان‌های معطلی برابر:

$$10\times1+9\times2+8\times3+...+1\times10$$

یعنی ۲۱۸ دقیقه و اگر به ترتیب عکس شماره‌هایشان در صف قرار گیرند آن‌گاه مجموع زمان‌های معطلی برابر:

$$10\times10+9\times9+8\times8+...+1\times1$$

یعنی ۳۸۵ دقیقه خواهد بود. حالت اول حداقل مجموع زمان‌های معطلی را دارد زیرا اگر نفر $i$ ام بعد از نفر $j$ ام ($i<j$) در صف قرار گیرند با جابه‌جایی آن دو نفر مجموع کل معطلی به اندازه‌ی $j-i$ دقیقه کاهش می‌یابد. به همین ترتیب ثابت می‌شود که حالت دوم نیز حداکثر مجموع زمان‌های معطلی را دارد.