====== سوال ۱۴ ======

در یک ایستگاه قطار، ریل‌ها به شکل زیر هستند:

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۸:148.png |}}

همه‌ی ریل‌ها از سمت چپ به راست یک طرفه هستند. اگر ‎۵‎ 
قطار با شماره‌های ‎۱‎ تا ‎۵‎ به ترتیب ‎۵‎ و ‎۴‎ و ‎۳‎ و ‎۲‎ و ‎۱‎ از ورودی
وارد این ریل‌ها شوند، کدام ترتیب برای خروج این قطارها ممکن   __نیست__؟ (قطارها می‌توانند هر یک از دو راه رسیدن به خروجی را انتخاب کنند و همچنین می‌توانند مدتی روی ریل منتظر 
بمانند، ولی نمی‌توانند از روی هم عبور کنند. همچنین
هر دو ریل به اندازه‌ی کافی طولانی هستند و می‌توانند
تعداد زیادی قطار را در خود جا دهند).‎

  - $4‎, ‎1‎, ‎2‎, ‎5‎, ‎3$‎
  - $4‎, ‎2‎, ‎1‎, ‎3‎, ‎5$‎
  - $2‎, ‎3‎, ‎4‎, ‎5‎, ‎1$‎
  - $2‎, ‎3‎, ‎5‎, ‎1‎, ‎4$‎
  - ‎$3‎, ‎4‎, ‎1‎, ‎5‎, ‎2$‎

<پاسخ>
گزینه (۲) درست است.


در دو ریل بالا و پایین دنباله‌ای نزولی وجود دارد٬ پس دنباله‌ی خروجی در درون خون دو دنباله‌ی نزولی دارد. دنباله‌ی گزینه ۱ را به دنباله‌های نزولی «$1,2,3$» و «$4,5$»٬ دنباله‌ی گزینه ۳ را به دنباله‌های نزولی «۱» و «$2,3,4,5$»٬ دنباله‌ی گزینه ۴ را به دنباله‌ای نزولی «$1,4$» و «$2,3,5$» و بالاخره دنباله گزینه ۵ را به دنباله‌های نزولی «$1,2$» و «$1,4,5$» تجزیه می‌کنیم. ولی گزینه‌ی ۲ امکان تجزیه شدن به دو دنباله‌ی نزولی را ندارد.


</پاسخ>
  * [[سوال ۱۵|سوال بعد]]
  * [[سوال ۱۳|سوال قبل]]