سوال ۲۳

یک ردیف از قطار با شماره‌های ۱ تا ۱۰ پشت سر هم مطابق شکل زیر قرار دارند. این ردیف را با دنباله‌ی $\langle 1, 2, 3, ..., 10\rangle$ نمایش می‌دهیم. قطار ۱ آخرین قطار است. بین ریل ورودی و ریل خروجی ریلی به نام «پارکینگ» دقیقاً مطابق زیر قرار گرفته است. هر قطار برای آن‌که در ریل خروجی ظاهر شود باید ابتدا به پارکینگ وارد شود. همیشه هم آخرین قطار موجود در پارکینگ دنده عقب به خروجی منتقل می‌شود. با این ترتیب در خروجی یک دنباله از قطارها (به ترتیب از راست به چپ) ظاهر خواهد شد که با $\langle a_1, a_2, ..., a_{10}\rangle$ نشان می‌دهیم و به آن دنباله‌ی «قابل تولید» می‌گوییم. دقت کنید که $a_1$ آخرین قطاری است که خارج می‌شود. چند تا از دنباله‌های زیر قابل تولید هستند؟

$\langle 10, 9, 8, 7, 4, 6, 3, 2, 1, 5\rangle$
$\langle 9, 9, 1, 6, 7, 5, 1, 3, 2, 10\rangle$
$\langle 8, 6, 7, 1, 10, 5, 4, 3, 9, 2\rangle$
$\langle 10, 9, 8, 1, 7, 6, 5, 3, 2, 4\rangle$

پاسخ

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

دنباله‌ی اول قابل تولید نیست. زیرا باید از قطار ۱۰ تا قطار ۵ وارد پارکینگ شوند و قطار ۵ خارج شود و سپس قطارهای ۴ تا ۱ وارد پارکینگ شوند و از آن طرف ۱ تا ۳ خارج شوند. ولی قطار ۴ هنوز خارج نشده است و قطار ۶ نمی‌تواند قبل از آن به خروجی رود.

دنباله‌ی دوم قابل تولید نیست زیرا قطار شماره‌ی ۴ ندارد و دوتا ۹ دارد.

دنباله‌ی سوم هم قابل تولید نیست. زیرا باید قطارهای ۱۰ تا ۲ به ترتیب وارد پارکینگ بشوند و سپس قطار ۲ خارج شود ولی بعد از آن قطار شماره ۹ نمی‌تواند خارج شود.

دنباله‌ی چهارم قابل تولید است. ابتدا قطارهای ۱۰ تا ۴ وارد پارکینگ می‌شوند. سپس قطار ۴ خارج می‌شود و قطارهای ۳ و ۲ وارد می‌شوند و قطار ۲ و ۳ خارج می‌شوند و بعد از آن قطار ۵ تا ۷ که از قبل در پارکینگ بودند خارج خواهند شد و بعد از آن قطار ۱ وارد و خارج می‌شود و در نهایت هم قطارهای ۸ تا ۱۰ خارج می‌شوند.