سوال ۱۴

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

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

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

پاسخ

گزینه (۲) درست است.

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