ﮐﺎﻫﺶ جایگشت

فرض کنید ‎$<\pi_1,\pi_2,\ldots,\pi_n>$‎ یک جایگشت از اعداد ‎1‎ تا ‎$n$‎ باشد. عملیات کاهش را روی این جایگشت به شکل زیر تعریف می کنیم:

• ‎همه اندیس‌هایی مانند ‎$i$‎ را پیدا می‌کنیم که ‎$\pi_i < \pi_{i-1}$‎ باشد.
• ‎همه اندیس‌هایی را که در مرحله ‎1‎ پیدا کردیم را، از جایگشت حذف می‌کنیم.

به عنوان مثال اگر عملیات کاهش را ‎$3$‎ بار روی جایگشت ‎$<6,3,4,2,1,5>$‎ انجام دهیم، به یک جایگشت شامل یک عدد ‎۶‎ می‌رسیم‎: ‎ $$<6,3,4,2,1,5> \rightarrow <6,4,5> \rightarrow <6,5> \rightarrow <6>$$ ‎ به جایگشت ‎$<\pi_1,\pi_2,\ldots,\pi_n>$‎ یک جایگشت زیبا می‌گوییم اگر بعد از حداکثر ‎$k$‎ بار اجرای عملیات کاهش، به یک جایگشت شامل تنها عدد ‎$n$‎ تبدیل شود. به عنوان مثال اگر ‎$n=6$‎ و ‎$k \geq 3$‎ باشد، جایگشت بالا یک جایگشت زیبا است.

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

$6$- الف ($8$ نمره) : اگر ‎$n=7$‎ و ‎$k = 4$‎ باشد و تعداد جایگشت‌های زیبا را ‎$M_1$‎ بنامیم، باقی‌مانده‌ی تقسیم ‎$M_1^3$‎ بر ‎$\Delta$‎ چند است؟

$6$- ب ($12$ نمره) : اگر ‎$n = 11$‎ و ‎$k = 5$‎ باشد و تعداد جایگشت‌های زیبا را ‎$M_2$‎ بنامیم، باقی‌مانده‌ی تقسیم ‎$M_2^3$‎ بر ‎$\Delta$‎ چند است؟

$6$- ج ($20$ نمره) : اگر ‎$n=\lfloor \frac{\Delta}{10}\rfloor$‎ و ‎$k = 200$‎ باشد و تعداد جایگشت‌های زیبا را ‎$M_3$‎ بنامیم، باقی‌مانده‌ی تقسیم ‎$M_3^3$‎ بر ‎$\Delta$‎ چند است‎؟

• سوال قبل