دنباله‌ی $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$ مرحله مرتب کرد.

• سوال بعد