دنباله $A$ شامل $n^2$ عدد طبیعی، داده شده است. می دانیم هریک از اعداد ۱ تا $n$ دقیقا $n$ بار در این دنباله آمده اند. میخواهیم این دنباله را به صورت صعودی مرتب کنیم. در هر مرحله میتوان $n$ عضو این دنباله را انتخاب کرده و آنها را به یک ترتیب دلخواه در مکانهای قبلی شان نوشت. می خواهیم در کمترین تعداد مرحله، دنباله را مرتب کنیم. به عنوان مثال، دنباله زیر در دو مرحله مرتب می شود:$$ \lt 1,1, \underline 2, \underline 3, 2,3, 2,3,\underline1 \gt \Rightarrow \lt 1,1,1,2,2,\underline 3,\underline2,3,\underline3 \gt \Rightarrow \lt 1,1,1,2,2,2,3,3,3 \gt $$

ثابت کنید هر دنباله دلخواه $A$ را می توان حداکثر در $n+1$ مرحله مرتب کرد.

• سوال بعد