المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی اول:دوره‌ی ۹:سوال ۲۶

سوال ۲۶

یک جدول $1\times10$ شامل اعداد ۱ تا ۱۰ است و از هر عدد دقیقا یک بار در جدول آمده است. در هر مرحله عدد $i$ بین ۱ تا ۱۰ را انتخاب می‌کنیم و اگر محتوای خانه‌ی $i$ام جدول برابر $(j \neq i)j$ بود٬ محتوای دو خانه‌ی $i$ام و $j$ام را عوض می‌کنیم. کدام یک از گزینه‌های زیر صحیح است؟

  1. تعداد تعویض‌ها می‌تواند بی‌نهایت باشد.
  2. تعداد تعویض‌ها حداکثر ۱۰ است.
  3. تعداد تعویض‌ها حداکثر ۴۵ است.
  4. تعداد تعویض‌ها حداکثر ۹ است.
  5. تعداد تعویض‌ها حداکثر ۲۰ است.

پاسخ

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

در هر مرحله تعویض٬ عدد $i$ در خانه‌ی $i$ قرار می‌گیرد یعنی در هر مرحله تعویض حداقل یک عنصر در جای خود قرار می‌گیرد بنابراین حداکثر ۹ تعویض لازم است( لازم به ذکر است که اگر دقیقا ۹ عدد در جایگاه خود باشند عدد دهم نیز به ناچار در جایگاه خود خواهد بود).


ابزار صفحه