سوال ۱۴
در یک ایستگاه قطار، ریل‌ها به شکل زیر هستند:
همه‌ی ریل‌ها از سمت چپ به راست یک طرفه هستند. اگر ۵ قطار با شماره‌های ۱ تا ۵ به ترتیب ۵ و ۴ و ۳ و ۲ و ۱ از ورودی وارد این ریل‌ها شوند، کدام ترتیب برای خروج این قطارها ممکن نیست؟ (قطارها می‌توانند هر یک از دو راه رسیدن به خروجی را انتخاب کنند و همچنین می‌توانند مدتی روی ریل منتظر بمانند، ولی نمی‌توانند از روی هم عبور کنند. همچنین هر دو ریل به اندازه‌ی کافی طولانی هستند و می‌توانند تعداد زیادی قطار را در خود جا دهند).
- $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$» تجزیه می‌کنیم. ولی گزینه‌ی ۲ امکان تجزیه شدن به دو دنباله‌ی نزولی را ندارد.