سوال ۲

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

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

ثابت کنید:

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