المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:تئوری:سوال ۲

سوال ۲

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

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

ثابت کنید:

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

ابزار صفحه