المپدیا

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

ابزار کاربر

ابزار سایت


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

جایگشت منتظم

جایگشت $\pi$ از مجموعه‌ی $\{1,2,…,n\}$ را منتظم می‌نامیم اگر برای هر $(1\leq i \leq n)i$، مقدار $|\pi (i)-i|$ ثابت باشد. تعداد جایگشت‌های منتظم را به ازای $n=1996$ پیدا کنید.

$\pi (i)$ عددی است که در جای $i$ ام جایگشت قرار گرفته است. به عنوان مثال، اگر جایگشت $\pi=(3,1,2,4)$ برای مجموعه‌ی $\{1,2,3,4\}$ را در نظر بگیریم، آن‌گاه $\pi (3)=2،\pi (2)=1،\pi (1)=3$ و $\pi (4)=4$.

پاسخ

فرض کنید $|\pi (i)-i|=k$. بنابراین $\pi (i)$ برابر با $k+1$ و یا $i-k$ است که مورد اخیر به ازای $k\geq i$ غیر قابل قبول است. پس برای هر $1\leq i \leq k$ داریم $\pi (i) =k+i$. حالا ادعا می‌کنیم که برای هر $1\leq i \leq k$ داریم $\pi (k+i)=i$ چون در غیر این صورت باید برای هر $j\geq 1$ داشته باشیم $\pi (jk+i)=(i+1)k+i$. حالا ادعا می‌کنیم که برای هر $1\leq i \leq k$ داریم $\pi (k+i)=i$. با همین استدلال خواهیم داشت: $\pi((2j-1)k+i)=2jk+i$ (برای هر $j\geq 1$ و $1\leq i \leq k$). بنابراین جایگشت $\pi$ برای هر $j$، مجموعه‌ی $\{kj+1,…,kj+k\}$ را به مجموعه‌ی $\{kj+k+1,…,kj+2k\}$ می‌برد. بنابراین باید $n$ مضربی از $2k$ باشد. پس تعداد جایگشت‌های منتظم غیر از حالت بدیهی $k=0$، برابر است با تعداد مقسوم‌علیه‌های $\frac{n}{2}$. یعنی برای $n=1996$، ۵ جایگشت منتظم داریم.


ابزار صفحه