Processing math: 14%

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

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

بنا بر تعریف هوشنگ جایگشت 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

تمام پاسخ‌های ارائه شده در این سوال با فرض \Delta = 10007 محاسبه شده‌اند.

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

پاسخ

2517

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

پاسخ

1559

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

پاسخ

5948