====== سوال ۱ ======


جایگشت ‎$\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$.


  * [[سوال ۲|سوال بعد]]