جایگشت ‎$\pi$‎ از اعداد ‎$1$‎ تا ‎$n$‎ داده شده است. دستگاهی داریم که عدد طبیعی ‎$k$‎ را از ما می‌گیرد و یک زیردنباله‌ی ‎$k$‎ - صعودی‌نزولی یا یک زیردنباله‌ی ‎$k$‎- نزولی‌صعودی را که طولش بیشینه باشد، از دنباله حذف می‌کند. کمترین تعداد مراحل برای حذف کل جایگشت را ‎$f(\pi)$‎ می‌نامیم. ‎$p(n)$‎ را بیشینه مقدار ‎$f$‎ در همه‌ی جایگشت‌های ‎$n$‎تایی بگیرید. ثابت کنید ‎$p(n)$‎ از ‎$\theta (\sqrt{n})$‎ است‎.

‎ به یک دنباله مثل ‎$a_1,a_2,\ldots,a_{r(k-1)+1}$ ‎ $k$-صعودی‌نزولی می‌گوییم اگر دنباله‌ی ‎$a_{t(k-1)+1},a_{t(k-1)+2},\ldots,a_{(t+1)(k-1)+1}$‎ به ازای هر ‎$t$‎ زوج که ‎$0 \leq t<r$‎ دنباله‌ای صعودی باشد و به ازای هر ‎$t$‎ فرد که ‎$0\leq t<r$‎ دنباله‌ای نزولی باشد‎. ‎ به یک دنباله مثل ‎ $a_1,a_2,\ldots,a_{r(k-1)+1}$ ‎ $k$-نزولی‌صعودی می‌گوییم اگر دنباله‌ی ‎$a_{t(k-1)+1},a_{t(k-1)+2},\ldots,a_{(t+1)(k-1)+1}$‎ به ازای هر ‎$t$‎ فرد که ‎$0 \leq t<r$‎ دنباله‌ای صعودی باشد و به ازای هر ‎$t$‎ زوج که ‎$0\leq t<r$‎ دنباله‌ای نزولی باشد‎. ‎ مثلا جایگشت ‎$\pi=1,5,2,7,6,3,4$‎ با ‎$k=4$‎ تبدیل به ‎$5,7,6$‎ می‌شود و با یک مرحله دیگر و ‎$k=2$‎ کار تمام است. با تعداد کمتری مرحله هم این کار امکان‌پذیر نیست. پس ‎$f(\pi)=2$.

• سوال بعد