فرض کنید $n$ و $k$ دو عدد طبیعی باشند ($k \le n$). در ابتدا جایگشتی نزولی از اعداد ۱ تا $n$ داریم. در هر مرحله می‌توانیم اعداد جایگشت را به $k$ دسته (نه لزوماً با تعداد برابر) تقسیم کنیم؛ سپس جایگشت جدید را به صورت زیر بسازیم:

ابتدا اعداد دسته‌ی یکم را به همان ترتیب جایگشت قبلی می‌نویسیم؛ سپس اعداد دسته‌ی دوم را به همان ترتیب جایگشت قبلی می‌نویسیم و همین‌طور الی آخر.

برای مثال فرض کنید $n=6$ و $k=3$ باشد. در این صورت جایگشت ابتدایی $\langle 6, 5, 4, 3, 2, 1 \rangle$ است. فرض کنید در مرحله‌ی یکم اعداد را به شکل زیر دسته‌بندی کنیم:

• دسته‌ی یکم: اعداد ۶ و ۳
• دسته‌ی دوم: اعداد ۵ و ۴ و ۱
• دسته‌ی سوم: عدد ۲

در این صورت جایگشت به شکل زیر در می‌آید: $$\langle 6, 3, 5, 4, 1, 2\rangle$$ کمینه‌ی تعداد مراحل لازم را برای مرتب‌سازی جایگشت بر حسب $n$ و $k$ بیابید.

• سوال قبل