در یک پشته اعداد $1,2,...,n$ به صورت دل‌خواه قرار دارند. در هر مرحله می‌توانیم تعدادی از اعداد بالای پشته را برداشته و به صورت معکوس در بالای پشته قرار دهیم. به عنوان مثال اگر $n=5$ باشد و ترتیب پشته $1,5,4,3,2$ باشد (۲ بالای پشته است) می‌توانیم با انتخاب سه عدد بالای پشته ترتیب را به صورت $1,5,2,3,4$ تغییر دهیم. هدف مرتب کردن اعداد به ترتیب یک‌نوا است به طوری که یک بالای پشته باشد.

1. ثابت کنید با $2n-2$ مرحله می‌توان اعداد را به هر ترتیبی که باشند، مرتب کرد.
2. ثابت کنید ترتیبی وجود دارد که تعداد مراحل لازم برای مرتب کردن آن از $n-1$ کم‌تر نیست.

• سوال بعد
• سوال قبل