المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۶:سوال ۱۳

سوال ۱۳

در سؤال قبل فرض کنید ۱۰ توپ در آرایشی به شکل زیر قرار گرفته‌اند:

در هر مرحله می‌توان سه توپ را که دوبه‌دو بر یک‌دیگر مماس هستند، انتخاب کرد و مثلث آن‌ها را یک واحد در جهت ساعت‌گرد چرخاند. برای مثال با اعمال این حرکت روی توپ‌های $2$، $3$ و $5$ در شکل بالا به شکل زیر می‌رسیم:

از حالت اولیه به چند آرایش متفاوت از $10!$ آرایش ممکن برای توپ‌ها می‌توانیم برسیم؟ (تعداد گام‌ها اهمیتی ندارد.)

  1. $10!$
  2. $\frac{10!}{2}$
  3. $\frac{10!}{3}$
  4. $\frac{10!}{6}$
  5. $9!$

پاسخ

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

اگر این توپ‌ها را به شکل یک جایگشت خطی ببینیم که در ابتدا مرتب‌شده نیز هستند، تعداد وارونگی‌های جایگشت زوج می‌ماند. پس به حداکثر نصف جایگشت‌ها می‌توانیم برسیم. رسیدن به نصف جایگشت‌ها نیز ممکن است.


ابزار صفحه