Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

جایگشت منتظم

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

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

پاسخ

فرض کنید |π(i)i|=k. بنابراین π(i) برابر با k+1 و یا ik است که مورد اخیر به ازای ki غیر قابل قبول است. پس برای هر 1ik داریم π(i)=k+i. حالا ادعا می‌کنیم که برای هر 1ik داریم π(k+i)=i چون در غیر این صورت باید برای هر j1 داشته باشیم π(jk+i)=(i+1)k+i. حالا ادعا می‌کنیم که برای هر 1ik داریم π(k+i)=i. با همین استدلال خواهیم داشت: π((2j1)k+i)=2jk+i (برای هر j1 و 1ik). بنابراین جایگشت π برای هر j، مجموعه‌ی {kj+1,,kj+k} را به مجموعه‌ی {kj+k+1,,kj+2k} می‌برد. بنابراین باید n مضربی از 2k باشد. پس تعداد جایگشت‌های منتظم غیر از حالت بدیهی k=0، برابر است با تعداد مقسوم‌علیه‌های n2. یعنی برای n=1996، ۵ جایگشت منتظم داریم.


ابزار صفحه