سوال ۱۸
دنباله‌ی $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$ واحد جابه‌جا شده است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
