المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۰:ترکیبیات:سوال ۶

سوال ۶

$d$ و $n$ اعدادی طبیعی هستند که $n$‌بر $d$ بخش‌پذیر است. فرض کنید $\pi$ یک جایگشت $n$‌ تایی است که تجزیه‌ی دوری آن شامل $d$ دور برابر است.(پس هر دور $\frac{n}{d}$ راسی است.) جایگشت $\sigma$ را $\pi$ـتوان گوییم اگر بتوان $\sigma$ را چند بار با خود ترکیب کرد و به $\pi$ رسید. (یعنی اگر عدد $m$ موجود باشد طوری که: $\sigma^m=\pi$)

ثابت کنید حداقل $d!$ جایگشت $\pi$ـتوان وجود دارد.


ابزار صفحه