سوال ۱۸

دنباله‌ی $a_1 , a_2 ,..., a_n$ از اعداد متمایز٬ یک دنباله‌ي «۲ـ مرتب» نامیده می‌شود اگر به ازای هر $1 \leq m \leq n-2$ ‎ داشته باشیم: $a_i < a_{i+2}$ . اگر یک دنباله ۲ـ مرتب را به ترتیب صعودی مرتب کنیم٬ هر یک از عضو‌های این دنباله حداکثر چند خانه جابه‌جا می‌شود؟ ( $\lfloor x \rfloor$ یعنی بزرگ‌ترین عدد صحیح کوچک‌تر یا مساوی $x$ و $\lceil x \rceil$ یعنی کوچک‌ترین عدد صحیح بزر‌گ‌تر یا مساوی $x$ .)

۲
۳
$\lfloor \frac{n}{2} \rfloor$
$\lceil \frac{n}{2} \rceil$
$n-1$

پاسخ

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

بیش‌ترین جابه‌جایی موقعی اتفاق می‌افتد که دنباله به صورت $a_1b_1a_2b_2…a_kb_k$ یا $a_1b_1a_2b_2…a_kb_ka_{k+1}$ بوده و هر دو دنباله‌ی $a_i$ ها و $b_i$ ها صعودی بوده و $b_k$ از $a_1$ کوچک‌تر باشد٬ در این صورت دنباله‌ی صعودی مورد نظر به شکل $b_1b_2…b_ka_1a_2…a_k$ یا $b_1b_2…b_ka_1a_2…a_{k+1}$ مرتب می‌شود و بیش‌ترین جابه‌جایی در این حالت مربوط به $b_k$ است که به اندازه‌ی $k$ واحد یا $\lfloor \frac{n}{2} \rfloor$ واحد جابه‌جا شده است.