سوال ۱
جایگشت π از اعداد 1 تا n داده شده است. دستگاهی داریم که عدد طبیعی k را از ما می‌گیرد و یک زیردنباله‌ی k - صعودی‌نزولی یا یک زیردنباله‌ی k- نزولی‌صعودی را که طولش بیشینه باشد، از دنباله حذف می‌کند. کمترین تعداد مراحل برای حذف کل جایگشت را f(π) می‌نامیم. p(n) را بیشینه مقدار f در همه‌ی جایگشت‌های nتایی بگیرید. ثابت کنید p(n) از θ(√n) است.
به یک دنباله مثل a1,a2,…,ar(k−1)+1 k-صعودی‌نزولی می‌گوییم اگر دنباله‌ی at(k−1)+1,at(k−1)+2,…,a(t+1)(k−1)+1 به ازای هر t زوج که 0≤t<r دنباله‌ای صعودی باشد و به ازای هر t فرد که 0≤t<r دنباله‌ای نزولی باشد. به یک دنباله مثل a1,a2,…,ar(k−1)+1 k-نزولی‌صعودی می‌گوییم اگر دنباله‌ی at(k−1)+1,at(k−1)+2,…,a(t+1)(k−1)+1 به ازای هر t فرد که 0≤t<r دنباله‌ای صعودی باشد و به ازای هر t زوج که 0≤t<r دنباله‌ای نزولی باشد. مثلا جایگشت π=1,5,2,7,6,3,4 با k=4 تبدیل به 5,7,6 می‌شود و با یک مرحله دیگر و k=2 کار تمام است. با تعداد کمتری مرحله هم این کار امکان‌پذیر نیست. پس f(π)=2.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
