سوال 14

۲۰ سکه با شماره‌های ۱ تا ۲۰ و وزن‌های متفاوت در اختیار داریم، ولی وزن هیچ‌یک از سکه‌ها را نمی‌دانیم. به صفی از سکه‌ها که از چپ به راست چیده شده‌اند « مرتب» می‌گوییم اگر هر سکه از سکه‌ی سمت راستش سبک‌تر باشد. دستگاه مرتب‌سازی در اختیار داریم که در هر بار استفاده ۱۰ سکه را می‌گیرد و صف مرتب آن‌ها را در خروجی تحویل می‌دهد. حداقل مقدار $k$ چند باید باشد که در هر حالتی با حداکثر $k$ بار استفاده از دستگاه بتوانیم صف مرتب همه‌ی سکه‌ها را ایجاد کنیم؟

  1. ۸
  2. ۶
  3. ۹
  4. ۵
  5. ۷

پاسخ

گزینه $(4)$ صحیح است