المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۲۴

سوال ۲۴

بر روی یک جایگشت $\langle a_8a_7...a_2a_1\rangle$ می‌توانیم دو عمل زیر را انجام دهیم:

  • عمل اول: تغییر آن به $\langle a_8a_6a_4a_2a_7a_5a_3a_1\rangle$
  • عمل دوم: تغییر آن به $\langle a_8a_4a_7a_3a_6a_2a_5a_1\rangle$

فرض کنید جایگشت اولیه $\langle 8, 7, 6, 5, 4, 3, 2, 1\rangle$ است. عدد $i$ را طلایی گوییم اگر با استفاده از دو عمل بالا بتوان جایگشتی تولید کرد که $a_i = ۲$ باشد. تعداد اعداد طلایی چندتاست؟

  1. ۳
  2. ۴
  3. ۵
  4. ۶
  5. ۸

پاسخ

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

گراف جایگشت متناسب با عملگرها را می‌کشیم و مکان‌هایی را که ۲ را به‌توان به آن‌جا منتقل کرد می‌یابیم. اعداد طلایی برابر ۲ و ۳ و ۵ می‌باشند که با هم یک دور را تشکیل داده‌اند.


ابزار صفحه