المپدیا

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

ابزار کاربر

ابزار سایت


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

نشاندن جایگشت‌ها

هوشنگ مدت‌ها است که بر روی جایگشت‌ها مطالعه می‌کند و به تازگی مفهوم نشاندن جایگشت‌ها را مطرح کرده که غوغایی بین جامعه جایگشت‌شناسان برپا کرده است.

بنا بر تعریف هوشنگ جایگشت $p$، جایگشت $q$ را می‌نشاند اگر دنباله‌ای از حرکات بشین سر جات وجود داشته باشد (طول این دنباله از حرکات می‌تواند صفر باشد) که جایگشت $p$ را به $q$ تبدیل کند. حرکت بشین سر جات $\boldsymbol{i}$ بر روی جایگشت $\langle p_1,p_2,\ldots,p_n\rangle$ اگر $p_i \neq i$ باشد، عضو $i$ ام و $p_i$ ام جایگشت را با یکدیگر جابه‌جا می‌کند و در غیر این صورت جایگشت را تغییر نمی‌دهد. در زیر یکی از دنباله‌هایی که جایگشت $\langle3,1,4,5,2\rangle$ را به $\langle1,2,4,3,5\rangle$ تبدیل می‌کند، آمده است.

$$\langle3,1,4,5,2 \rangle\xrightarrow{\text{ب.س.ج ۵}} \langle3,2,4,5,1 \rangle\xrightarrow{\text{ب.س.ج ۴}} \langle3,2,4,1,5 \rangle\xrightarrow{\text{ب.س.ج ۴}} \langle1,2,4,3,5 \rangle$$

$1$- الف ($14$ نمره) : اگر تعداد جایگشت‌هایی را که جایگشت $\langle2,3,5,9,8,7,10,1,4,6\rangle$ می‌نشاند، $x$ در نظر بگیریم. باقی مانده‌ی $x^4$ بر $\Delta$ چند است؟

$1$- ب ($10$ نمره) : اگر به ازای هر جایگشت با طول $10$، تعداد جایگشت‌هایی که می‌نشاند را حساب کرده و این اعداد را با هم جمع کنیم، باقی‌مانده‌ی این مجموع بر $\Delta$ چند خواهد بود؟

$1$- ج ($16$ نمره) : اگر به ازای هر جایگشت با طول $100$، تعداد جایگشت‌هایی که می‌نشاند را حساب کرده و این اعداد را با هم جمع کنیم، باقی‌مانده‌ی این مجموع بر $\Delta$ چند خواهد بود؟


ابزار صفحه