‎$n$‎ عدد کارت به شماره‌های ‎۱‎ تا ‎$n$‎ روی تعدادی میله قرار گرفته‌اند. ممکن است روی یک میله بیش از یک کارت باشد. در هر حرکت می‌توان تعداد دل‌خواهی کارت (مثلا ‎$i$‎‎ کارت) را از بالای یک میله (مثلاً میله‌ی ‎A‎) برداشت و روی یک میله‌ی دیگر (مثلاً میله‌ی ‎B‎) قرار داد در صورتی که دو شرط زیر برآورده شود:

• شماره‌ی ‎$i$‎ کارت برداشته‌شده پشت سرهم و از بالا به پایین نزولی باشد.
• یا میله‌ی ‎B‎ خالی باشد و یا عدد کارتی که روی میله‌ی ‎B‎ قرار دارد (که در واقع بالاترین کارت روی میله‌ی ‎B‎‎ است) یک شماره کم‌تر از پایین‌ترین کارتی باشد که از روی میله‌ی A‎ برداشته‌ایم.

ثابت کنید:

• اگر تعداد میله‌ها بیش‌تر از ‎$\frac{n+1}{2}$‎ باشد، می‌توان با این اعمال همه‌ی کارت‌ها را روی یک میله مرتب قرار داد به طوری‌که کارت با شماره‌ی ‎$n$‎ بالاترین کارت آن میله باشد.
• برای ‎$n > 2$‎ اگر تعداد میله‌ها حداکثر ‎$n‎ / ‎2$‎ باشد، لزوماً نمی‌توان کارت‌ها را به این شکل مرتب کرد.

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