سوالات المپیاد:مرحله ی اول:دوره ی ۲۰:سوال ۲۴
سوال ۲۴
بر روی یک جایگشت ⟨a8a7...a2a1⟩ می‌توانیم دو عمل زیر را انجام دهیم:
- عمل اول: تغییر آن به ⟨a8a6a4a2a7a5a3a1⟩
- عمل دوم: تغییر آن به ⟨a8a4a7a3a6a2a5a1⟩
فرض کنید جایگشت اولیه ⟨8,7,6,5,4,3,2,1⟩ است. عدد i را طلایی گوییم اگر با استفاده از دو عمل بالا بتوان جایگشتی تولید کرد که ai=۲ باشد. تعداد اعداد طلایی چندتاست؟
- ۳
- ۴
- ۵
- ۶
- ۸
پاسخ
گزینه‌ی (۱) درست است.
گراف جایگشت متناسب با عملگرها را می‌کشیم و مکان‌هایی را که ۲ را به‌توان به آن‌جا منتقل کرد می‌یابیم. اعداد طلایی برابر ۲ و ۳ و ۵ می‌باشند که با هم یک دور را تشکیل داده‌اند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
